本文主要是介绍线性表基础：栈（五）智?发散题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

智⼒发散题

推荐刷题顺序：
LeetCode #636 函数的独占时间
LeetCode #1124 表现良好的最⻓时间段
Leecode #54 螺旋矩阵

1. LeetCode #636 函数的独占时间

题目描述：
有一个 单线程 CPU 正在运行一个含有 n 道函数的程序。每道函数都有一个位于 0 和 n-1 之间的唯一标识符。

函数调用 存储在一个 调用栈 上 ：当一个函数调用开始时，它的标识符将会推入栈中。而当一个函数调用结束时，它的标识符将会从栈中弹出。标识符位于栈顶的函数是 当前正在执行的函数 。每当一个函数开始或者结束时，将会记录一条日志，包括函数标识符、是开始还是结束、以及相应的时间戳。

给你一个由日志组成的列表 logs ，其中 logs[i] 表示第 i 条日志消息，该消息是一个按 “{function_id}:{“start” | “end”}:{timestamp}” 进行格式化的字符串。例如，“0:start:3” 意味着标识符为 0 的函数调用在时间戳 3 的 起始开始执行 ；而 “1:end:2” 意味着标识符为 1 的函数调用在时间戳 2 的 末尾结束执行。注意，函数可以 调用多次，可能存在递归调用 。

函数的 独占时间 定义是在这个函数在程序所有函数调用中执行时间的总和，调用其他函数花费的时间不算该函数的独占时间。例如，如果一个函数被调用两次，一次调用执行 2 单位时间，另一次调用执行 1 单位时间，那么该函数的 独占时间 为 2 + 1 = 3 。

以数组形式返回每个函数的 独占时间 ，其中第 i 个下标对应的值表示标识符 i 的函数的独占时间。

解题思路：
可以使用栈来模拟函数的调用，即在遇到一条包含 start 的日志时，我们将对应的函数 id 入栈；在遇到一条包含 end 的日志时，我们将对应的函数 id 出栈。在每一个时刻，栈中的所有函数均为被调用的函数，而栈顶的函数为正在执行的函数。

思路一：

• 当碰到一个新任务启动的时候，需要把之前的时间加给上一个任务
• 当碰到一个任务结束的时候，需要把当前的时间段加给当前任务

实现，用pre记录上一个函数的开始或结束的时间点：

• 我们依次遍历所有的日志，对于第 i 条日志，如果它包含 start，那么栈顶函数从其时间戳 time[i] 开始运行，即 prev = time[i]；如果它包含 end，那么栈顶函数从其时间戳 time[i] 的下一个时间开始运行，即 prev = time[i] + 1。
• 对于第 i + 1 条日志，如果它包含 start，那么在时间戳 time[i + 1] 时，有新的函数被调用，因此原来的栈顶函数的独占时间为 time[i + 1] - prev；如果它包含 end，那么在时间戳 time[i + 1] 时，原来的栈顶函数执行结束，独占时间为 time[i + 1] - prev + 1。
• 在这之后，我们更新 prev 并遍历第 i + 2 条日志。在遍历结束后，我们就可以得到所有函数的独占时间。

class Solution {
    public int[] exclusiveTime(int n, List<String> logs) {
        int[] result = new int[n];
        LinkedList<Integer> stack = new LinkedList<>();// 记录函数的调用过程，维护函数ID
        Long pre = 0L;
        for (int i = 0; i < logs.size(); i++) {
            String[] split = logs.get(i).split(":");
            Integer functionId = Integer.valueOf(split[0]);// 函数ID
            String status = split[1];// start或end
            Long timestamp = Long.valueOf(split[2]);// 时间戳

            if ("start".equals(status)) {
                if (!stack.isEmpty()) {
                    // 不为空，将当前经历的时间，记录到栈顶函数
                    result[stack.peek()] += (timestamp - pre);
                }
                // 新的函数进栈
                stack.push(functionId);
                pre = timestamp;
            } else {
                // "end"
                // 将当前经历的时间，记录到栈顶函数
                result[stack.peek()] += (timestamp - pre + 1);
                // 函数出栈
                stack.pop();
                pre = timestamp + 1;
            }
        }
        return result;
    }
}

思路二：

• 遇到 start 日志时，直接将对应的函数入栈，不做任何其他处理
• 遇到 end 日志时，则将栈顶函数出栈，同时计算消耗的时间并累加给该出栈的函数，此时如果栈中不为空，说明当前出栈函数的执行时间是被包含在此时栈顶函数的执行时间中的，所以还需要将此时栈顶函数对应的独占时间减去当前这个出栈函数消耗的时间
• 重复上述操作直到遍历结束，就可以得到所有函数的独占时间

遇到start入栈不做任何处理：

遇到end，将栈顶函数出栈，同时计算消耗的时间，累加给对应函数：

此时由于栈中还有元素，说明当前出栈函数1的执行时间是被包含在此时栈顶函数0的执行时间中的，所以函数0的独占时间需要减去此时出栈函数1消耗的时间：

继续处理，遇到end，将栈顶函数出栈，同时计算消耗的时间，累加给对应函数：

由于此时栈为空，所以不需要在做其他操作，最终处理完所有log得到所有函数的独占时间。

class Solution {
    class Task {
        public Task(String log) {
            String[] split = log.split(":");
            id = Integer.valueOf(split[0]);// 函数ID
            time = Integer.valueOf(split[2]);// 时间戳
            isStart = "start".equals(split[1]);// start或end
        }

        int id;
        int time;
        boolean isStart;
    }

    public int[] exclusiveTime(int n, List<String> logs) {
        int[] result = new int[n];// 结果数组
        LinkedList<Task> stack = new LinkedList<>();// 函数栈
        for (String log : logs) {
            Task curTask = new Task(log);
            if (curTask.isStart) {
                // start直接入栈
                stack.push(curTask);
            } else {
                // end弹栈并计算消耗时间
                Task pop = stack.pop();
                Integer duration = curTask.time - pop.time + 1;
                result[curTask.id] += duration;
                if (!stack.isEmpty()) {
                    // 此时如果栈不为空，将栈顶函数对应的独占时间 减去弹栈的函数独占时间
                    result[stack.peek().id] -= duration;
                }
            }
        }
        return result;
    }
}

2. LeetCode #1124 表现良好的最⻓时间段

题目描述：
给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。

我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。

所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。

请你返回「表现良好时间段」的最大长度。

解题思路：

• 如果把表现“良好”记为+1，把表现“不好”记为-1，将原序列转化为正负1的序列，原问题就转化为求转化后序列的最⻓⼀段连续⼦序列，使得⼦序列的和⼤于0。

  
  接下来需要再这个序列中找到最长的一段（区间），让他们相加和 > 0

• 而处理区间和，可以引⼊“前缀和”的技巧。前缀和数组的第n项，就是原数组前n项的和。然后在前缀和数组最前面补⼀个0，表⽰前0项之和，即不取任何元素的情况。

  

• 这样就可以将“区间和”转化为“前缀和”之差来计算。此时，原数组的区间和 就等于前缀和数组上的两项相减

  

• 在前缀和数组上求解问题，等价于在原序列上求解问题，这道题最终转换为在前缀和数组中找到：后一项减去前面某一项，值是大于0，并且这两项区间是最长的一段。

  具体实现可以通过遍历前缀和数组中的每一位，从当前位向前找，找到离当前位置最远并且值小于当前位置值的位置，而最远的位置其实就是数组从左开始第一个小于当前位置值的位置，这两个位置之间的距离就是当前位置的最优解，最后从遍历的每个结果中取最大值即可。

class Solution {
    public int longestWPI(int[] hours) {
        int longestWPI = 0;
        // 大于8h，记为1，否则记为-1
        // [9,9,6,0,6,6,9] => 1,1,-1,-1,-1.-1,1
        // 前缀和：1,2,1,0,-1,-2.-1
        // 如果想求第二天到第四天时间段的表现情况，可以用第四天前缀和的减去第一天的前缀和
        // 0-1 =-1，如果直接计算也可得 1-1-1 = -1
        // 如果求第一天到第四天的怎么办？要用第四天减去第0天，即在前缀和数组最前面补一个0
        int[] prefixSum = new int[hours.length + 1];
        // 表示前0项的前缀和
        prefixSum[0] = 0;
        // 假设存在[y,x]，y<x，这个时间段是表现良好的时间段，那么有x的前缀和 - y的前缀和 >0
        // 即 x的前缀和 > y 的前缀和
        // 如果要求最大长度，要保证y尽可能小，即越靠左，其实就是找到在前缀和数组从左开始第一个小于当前位置值的元素 的位置

        for (int i = 0; i < hours.length; i++) {
            // 求前缀和
            prefixSum[i + 1] = prefixSum[i] + (hours[i] > 8 ? 1 : -1);
            // 求 从左开始第一个小于当前位置值的元素 的位置
            int leftIndex = -1;
            for (int j = 0; j < i + 1; j++) {
                if (prefixSum[j] < prefixSum[i + 1]) {
                    leftIndex = j;
                    break;
                }
            }
            if (leftIndex != -1) {
                longestWPI = Math.max(longestWPI, i + 1 - leftIndex);
            }
        }

        return longestWPI;
    }
}

• 上面的推导还可以继续优化，我们可以定义一个函数f(n-1)代表值为n-1作为结尾的最长序列长度，那么有f(n) = f(n-1) + p(n) - p(n-1)，其中p代表对应值的下标位置。这里需要注意f(n-1)中的n-1这个值一定要是第一次出现，而p(n)中的n是遍历的当前位置的值。（自己画一个前缀和的xy坐标图就知道了）

  下图是该题前缀和数组的一种情况：
  
  如果用第二个-2，则 f(-2) = 1，p(-2) = 6
  则f(-1) = f(-2) + p(-1) - p(-2) = 1 + 7 - 6 = 2

这样我们就推导出了一个基于f(n)函数的递推公式。

class Solution {
    public int longestWPI(int[] hours) {
        int longestWPI = 0;
        HashMap<Integer, Integer> numIndex = new HashMap<>();// 记录已经计算出最长序列长度的值对应的索引（该索引为该值第一次出现的位置）
        HashMap<Integer, Integer> numResult = new HashMap<>();// 记录第一次出现的值所计算出的最长序列长度
        numIndex.put(0, -1);// 前缀和数组从0开始，所以我们记录值0第一次出现的位置为-1
        numResult.put(0, 0);// 初始化值为0的最长序列长度为0
        // cnt统计前缀和
        for (int i = 0, cnt = 0; i < hours.length; i++) {
            // 求前缀和
            cnt += (hours[i] > 8 ? 1 : -1);
            // 判断numIndex中是否计算过这个值，只有第一次出现才需要计算
            if (!numResult.containsKey(cnt)) {
                numIndex.put(cnt, i);// 记录该值第一次出现的索引位置
                // 判断是否计算过cnt-1的最长序列长度
                if (!numResult.containsKey(cnt - 1)) {
                    // 如果没有，当前值计算出的最长序列长度为0
                    numResult.put(cnt, 0);
                } else {
                    // 否则利用推导的公示f(n) = f(n-1) + p(n) - p(n-1)
                    numResult.put(cnt, numResult.get(cnt - 1) + i - numIndex.get(cnt - 1));
                }
            }
            // 当前值为cnt，要往前找值为cnt-1的那个位置，没找到就过
            if (!numIndex.containsKey(cnt - 1)) {
                continue;
            }
            // 找到了就和已经存的最长序列比较一下，取最大值
            longestWPI = Math.max(longestWPI, i - numIndex.get(cnt - 1) + numResult.get(cnt - 1));
        }
        return longestWPI;
    }
}

• 终极优化，首先在前缀和数组中，如果当前位置值 > 0，那么当前位置到起始位置这一段区间就是当前的最长序列长度

  

• 当当前位置值 n <= 0时，我们就需要往前找第一个小于当前位置值的位置，如果这个位置存在，它一定是第一个值为n-1的位置，为什么？假设当前位置前面存在比n小的值，n-1,n-2,n-3…由于原序列由1和-1组成，这种特殊性导致前缀和数组中的值一定是连续的，比如当前位置值为0，那么下一位只有可能是1或者-1，又因为整个前缀和数组是从0开始，所以如果存在n-2，它前面必然存在n-1，所以往前找第一个小于当前位置值的位置，只需要找第一个值为n-1的位置。

  

class Solution {
    public int longestWPI(int[] hours) {
        int sum = 0;// 计算前缀和
        int res = 0;// 结果
        HashMap<Integer, Integer> sumToIndex = new HashMap<>();// 统计前缀和数组中所有负数第一次出现的位置
        for (int i = 0; i < hours.length; i++) {
            sum += (hours[i] > 8 ? 1 : -1);

            if (sum > 0) {
                // 如果当前位置值 > 0，那么当前位置到起始位置这一段区间就是当前的最长序列长度
                res = i + 1;
            } else {
                if (!sumToIndex.containsKey(sum)) {
                    // 维护前缀和数组中小于等于0的值第一次出现的索引
                    sumToIndex.put(sum, i);
                }
                if (sumToIndex.containsKey(sum - 1)) {
                    // 要往前找第一个小于当前位置值的位置，只需要找第一个值为n-1的位置
                    res = Math.max(res, i - sumToIndex.get(sum - 1));
                }
            }
        }
        return res;
    }
}

3. Leecode #54 螺旋矩阵：

题目描述：
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

解题思路：
可以将矩阵看成若干层，首先输出最外层的元素，其次输出次外层的元素，直到输出最内层的元素。假设矩阵左上角位于 (top,left)，右下角位于 (bottom,right)，按照如下顺序遍历当前层的元素。

• 从左到右遍历上侧元素，依次为(top,left) 到(top,right)。
• 从上到下遍历右侧元素，依次为 (top+1,right) 到 (bottom,right)。
• 如果 left<right 且 top<bottom，则从右到左遍历下侧元素，依次为 (bottom,right−1) 到 (bottom,left+1)，以及从下到上遍历左侧元素，依次为 (bottom,left) 到 (top+1,left)。

遍历完当前层的元素之后，将 left 和 top 分别增加 1，将 right 和 bottom 分别减少 1，进入下一层继续遍历，直到遍历完所有元素为止。

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        int top = 0, left = 0, bottom = matrix.length - 1, right = matrix[0].length - 1;
        while (top <= bottom && left <= right) {
            // 从左到右遍历上侧元素，依次为(top,left) 到(top,right)。
            for (int column = left; column <= right; column++) {
                result.add(matrix[top][column]);
            }
            // 从上到下遍历右侧元素，依次为 (top+1,right) 到 (bottom,right)。
            for (int row = top + 1; row <= bottom; row++) {
                result.add(matrix[row][right]);
            }
            if (left < right && top < bottom) {
                // 从右到左遍历下侧元素，依次为 (bottom,right−1) 到 (bottom,left)
                for (int column = right - 1; column >= left; column--) {
                    result.add(matrix[bottom][column]);
                }
                // 从下到上遍历左侧元素，依次为 (bottom-1,left) 到 (top+1,left)。
                for (int row = bottom - 1; row > top; row--) {
                    result.add(matrix[row][left]);
                }
            }
            top++;
            left++;
            bottom--;
            right--;
        }
        return result;
    }
}

这篇关于线性表基础：栈（五）智?发散题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！