《代码随想录》单调栈：高性能Java实现与详细图解

🎯 本文深入探讨了单调栈在解决多种算法问题中的应用，包括“每日温度”、“下一个更大元素”系列以及“接雨水”等问题。通过详细分析基础实现与优化策略，展示了如何利用单调栈有效地寻找数组中任一元素左右第一个大于或小于它的元素位置，从而提高算法效率。文中不仅提供了详尽的Java代码示例，还对比了不同方法之间的差异和优势，旨在帮助读者掌握单调栈的核心思想，并能灵活应用于实际编程挑战中。此外，文章也介绍了双指针等替代方案，为解决问题提供了多角度思考路径。

什么时候使用单调栈？

通常一维数组中，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，就可以使用单调栈

每日温度

https://leetcode.cn/problems/daily-temperatures/description/

基础实现

【思路】

• 创建一个单调栈，从栈底到栈顶，元素单调递减，注意存储的是元素的索引，然后直接凭借索引去 temperatures 获取元素即可
• 遍历 temperatures 的元素
  • 如果遍历到的元素 > 栈顶元素，说明栈顶的那一天的下一个更高温度就是当前这一天，更新栈顶元素对应下一更高温度天数，弹出栈顶元素，继续检查新的栈顶元素
  • 如果遍历到的元素 <= 栈顶元素，将单元元素的索引压入栈单调中

单调栈的作用是帮助我们记录那些还没有找到下一个更高温度的日子，其中栈顶的温度是最小的。当我们遇到一个比栈顶温度高的温度时，说明栈顶的那一天的下一个更高温度已经找到了，我们就可以更新 answer 数组，并将栈顶元素弹出。

如果还是不理解，可以看下图的迭代流程

public int[] dailyTemperatures(int[] temperatures) {
    int[] answer = new int[temperatures.length];
    // 创建一个单调栈，从栈底到栈顶，元素单调递减
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < temperatures.length; i++) {
        // --for-- 遍历数组
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            // --if-- 如果栈不为空，且当元素>栈顶元素，弹出栈顶元素，并设置栈顶元素对应的下一个更高温度出现在几天后
            Integer index = stack.pop();
            answer[index] = i - index;
        }
        stack.push(i);
    }
    return answer;
}

优化

使用数组来模拟栈，减少ArrayDeque的对象创建以及其他开销，数组操作效率更高

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] answer = new int[n];
    int[] stack = new int[n]; // 用数组模拟栈
    int top = -1; // 栈顶指针

    for (int i = 0; i < n; i++) {
        while (top >= 0 && temperatures[i] > temperatures[stack[top]]) {
            int index = stack[top--]; // 弹出栈顶元素
            answer[index] = i - index;
        }
        stack[++top] = i; // 压入当前索引
    }
    return answer;
}

下一个更大元素 I

https://leetcode.cn/problems/next-greater-element-i/description/

基础实现

题目问我们是否可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案？

说明每个数组我们只能遍历一次，因此可以使用一个 Map 来记录 num1 中元素出现的位置，这样在遍历num2的时候，可以很快判断所遍历元素是否在 num1 中，并知道其在 num1 中的索引

剩下的事情就是单调栈的事情了，思路和上一题大致相同。只不过这里的栈直接存储元素即可，不需要存储元素对应的索引，因为它要找的是下一个更大的元素，而不是下一个更大的元素在多远之后

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    int[] ans = new int[nums1.length];
    // 首先将数组填充为-1，因为找不到下一个更大元素的位置要是 -1
    Arrays.fill(ans, -1);
    // 遍历 nums1 ，将元素以及其索引存储到字典中，方便后续查询
    HashMap<Integer, Integer> numAndIndexMap = new HashMap<>();
    for (int i = 0; i < nums1.length; i++) {
        numAndIndexMap.put(nums1[i], i);
    }
    // 声明一个单调栈
    Deque<Integer> stack = new ArrayDeque<>();
    for (int num : nums2) {
        while (!stack.isEmpty() && num > stack.peek()) {
            // --if-- 如果找到了比栈顶元素更大的元素
            // 将栈顶元素移除
            // 并设置该元素的下一个更大元素
            ans[numAndIndexMap.get(stack.pop())] = num;
        }
        if (numAndIndexMap.containsKey(num)) {
            // 如果当前元素也处于nums1中，将其压入栈中
            stack.push(num);
        }
    }
    return ans;
}

优化

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    // 初始化结果数组，默认值为 -1，表示没有找到下一个更大元素
    int[] ans = new int[nums1.length];
    Arrays.fill(ans, -1);

    // 使用数组代替哈希表，存储 nums1 中元素及其索引的映射关系
    int[] numToIndex = new int[10001];
    // 初始化为 -1，表示元素不存在于 nums1 中
    Arrays.fill(numToIndex, -1); 
    // 记录 nums1 中元素及其索引
    for (int i = 0; i < nums1.length; i++) {
        numToIndex[nums1[i]] = i; 
    }

    // 使用单调栈来找到 nums2 中每个元素的下一个更大元素
    Deque<Integer> stack = new ArrayDeque<>();
    for (int num : nums2) {
        // 当栈不为空且当前元素大于栈顶元素时，说明找到了栈顶元素的下一个更大元素
        while (!stack.isEmpty() && num > stack.peek()) {
            // 弹出栈顶元素
            int top = stack.pop(); 
            // 如果栈顶元素存在于 nums1 中
            if (numToIndex[top] != -1) { 
                // 更新结果数组
                ans[numToIndex[top]] = num; 
            }
        }
        // 如果当前元素存在于 nums1 中，将其压入栈中，等待后续处理
        if (numToIndex[num] != -1) {
            stack.push(num);
        }
    }

    return ans; // 返回结果数组
}

下一个更大元素II

https://leetcode.cn/problems/next-greater-element-ii/description/

【思路】

• 这道题主要是可以循环，为了解决这个问题，遍历两次即可
• 其他的地方没有难度，和前面两道题类似

public int[] nextGreaterElements(int[] nums) {
    int[] ans = new int[nums.length];
    Arrays.fill(ans, -1);
    // 存储元素对应的索引，方便后面更新 ans 数组
    ArrayDeque<Integer> stack = new ArrayDeque<>();
    // 把数组循环两次即可
    int num = nums.length * 2;
    for (int i = 0; i < num; i++) {
        int j = i % nums.length;
        while (!stack.isEmpty() && nums[j] > nums[stack.peek()]) {
            ans[stack.pop()] = nums[j];
        }
        stack.push(j);
    }
    return ans;
}

其实上面的代码还存在问题，我们在将数据压入栈中时，其实只需要前n次遍历的数据压入。后n次遍历如果还压入，那就是重复处理了，增加不必要的性能开销

public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];
    Arrays.fill(ans, -1);
    ArrayDeque<Integer> stack = new ArrayDeque<>();
    
    for (int i = 0; i < 2 * n; i++) {
        int j = i % n;
        // 如果当前元素大于栈顶元素对应的元素，则更新答案
        while (!stack.isEmpty() && nums[j] > nums[stack.peek()]) {
            ans[stack.pop()] = nums[j];
        }
        // 只有在第一轮循环时才将元素入栈，避免重复处理
        if (i < n) {
            stack.push(j);
        }
    }
    
    return ans;
}

接雨水

https://leetcode.cn/problems/trapping-rain-water/description/

单调栈

【单调栈】

创建一个单调栈，从栈底到栈顶，元素单调递减，注意栈中存储的是索引。栈的作用是找到每个“坑”的左右边界（即左右墙），并计算坑的面积。

【遍历数组】

• 从左到右遍历数组，依次处理每个高度。
• 对于当前遍历到的元素 heightArr[r]，将其与栈顶元素比较：
  • 如果 heightArr[r] 大于栈顶元素的高度，说明找到了一个右墙，可以形成一个“坑”。
  • 如果 heightArr[r] 等于栈顶元素的高度，更新栈顶元素（因为相同高度的墙不会形成新的坑）。
  • 如果 heightArr[r] 小于栈顶元素的高度，直接将其压入栈中。

【计算雨水量】

• 当 heightArr[r] 大于栈顶元素的高度时，弹出栈顶元素（表示坑的最低点），并计算当前坑的面积：
  • 宽度：右墙索引 r 减去左墙索引 l 再减 1，即 (r - l - 1)。
  • 高度：左右墙的最小高度减去坑的高度，即 Math.min(heightArr[l], heightArr[r]) - heightArr[m]。
• 将计算得到的面积累加到结果 result 中。

【注意】

• 如果栈为空，说明没有左墙，无法形成坑，直接跳过。
• 如果当前高度等于栈顶高度，弹出栈顶元素，避免重复计算。

如果看上面文字一面懵逼，可以看看下图中的示例迭代过程：

public int trap(int[] heightArr) {
    int result = 0;
    // 创建一个单调栈，从栈底到栈顶，元素单调递减
    Deque<Integer> stack = new ArrayDeque<>();
    for (int r = 0; r < heightArr.length; r++) {
        int right = heightArr[r];
        while (!stack.isEmpty() && right > heightArr[stack.peek()]) {
            // --if-- 如果当前元素 > 栈顶元素，弹出栈顶元素，当前元素表示坑的最低点
            int m = stack.pop();
            if (stack.isEmpty()) {
                // --if-- 看看栈中是否还有元素，没有的话，说明没有做墙壁，不形成坑，直接break即可
                break;
            }
            // 获取坑的左墙
            int l = stack.peek();
            // 填充坑的面积
            // 宽：右墙索引 - 左墙索引 - 1 ，即(r - l - 1)
            // 高：Math.min(左墙高度, 右墙高度) - 坑的高度，即(Math.min(heightArr[l], right) - heightArr[m])
            result += (r - l - 1) * (Math.min(heightArr[l], right) - heightArr[m]);
        }
        if (!stack.isEmpty() && right == heightArr[stack.peek()]) {
            // --if-- 如果说当前遍历高度 = 栈顶元素高度，先弹出栈顶元素
            stack.pop();
        }
        // 将当前遍历索引压入栈中
        stack.push(r);
    }
    return result;
}

双指针

初始化：

• 左指针 left 指向数组的起始位置（0）。
• 右指针 right 指向数组的末尾位置（heightArr.length - 1）。
• leftMax 和 rightMax 分别记录从左到右和从右到左遍历过程中的最大高度，初始值为 0。

遍历数组：

• 比较 heightArr[left] 和 heightArr[right] 的大小：
  • 如果 heightArr[left] < heightArr[right]，说明左边的柱子较低，先处理左指针。
    • 如果当前柱子高度 heightArr[left] 大于等于 leftMax，更新 leftMax。
    • 否则计算当前位置能接住的雨水量：leftMax - heightArr[left]，累加到结果中。
    • 移动左指针 left 向右。
  • 如果 heightArr[left] >= heightArr[right]，说明右边的柱子较低，先处理右指针。
    • 如果当前柱子高度 heightArr[right] 大于等于 rightMax，更新 rightMax。
    • 否则计算当前位置能接住的雨水量：rightMax - heightArr[right]，累加到结果中。
    • 移动右指针 right 向左。

终止条件：

• 当 left 和 right 相遇时，遍历结束。

如果看上面的流程感觉有点抽象，可以直接看下面的推导

public int trap(int[] heightArr) {
    // 左右指针
    int left = 0, right = heightArr.length - 1;
    // 初始化左右最大值
    int leftMax = 0, rightMax = 0;
    int result = 0;

    // 如果left==right，说明已经遍历完成
    while (left < right) {
        if (heightArr[left] < heightArr[right]) {
            // --if-- 左边柱子较低，处理左指针
            if (heightArr[left] >= leftMax) {
                // 更新 leftMax
                leftMax = heightArr[left]; 
            } else {
                // 计算雨水量
                result += leftMax - heightArr[left]; 
            }
            // 移动左指针
            left++; 
        } else {
            // --if-- 右边柱子较低，处理右指针
            if (heightArr[right] >= rightMax) {
                // 更新 rightMax
                rightMax = heightArr[right]; 
            } else {
                // 计算雨水量
                result += rightMax - heightArr[right]; 
            }
            // 移动右指针
            right--; 
        }
    }
    return result;
}

柱状图中最大的矩形

https://leetcode.cn/problems/largest-rectangle-in-histogram/description/

贪心

【思路】

遍历每一个柱子，同时尝试向左、向右搜索，直到搜索到比当前柱子更矮的柱子，停止搜索。以当前柱子为高度，能找到的最大面积为：(right-left-1)*当前柱子高度

public int largestRectangleArea(int[] heights) {
    int result = 0;
    int length = heights.length;
    for (int i = 0; i < heights.length; i++) {
        // --for-- 从当前柱状图开始搜索
        int left = i;
        int right = i;
        // 从左边开始探索，直到找到比当前更矮索引 left
        while (left >= 0) {
            if (heights[left] < heights[i]) {
                break;
            }
            left--;
        }
        // 从右边开始探索，直到找到比当前更矮索引 right
        while (right < length) {
            if (heights[right] < heights[i]) {
                break;
            }
            right++;
        }
        // 计算当前面积
        int temp = (right - left - 1) * heights[i];
        if (temp > result) {
            result = temp;
        }
    }
    return result;
}

部分案例超时

单调栈

扩展数组：

• 为了方便计算，在直方图的左右两边各加一个高度为0的柱子。
• 比如，heights = [2,1,5,6,2,3] 扩展后变成 newHeight = [0,2,1,5,6,2,3,0]。

使用单调栈：

• 用一个单调栈来存储柱子的索引。栈的特点是：栈中索引对应的柱子高度是从栈底到栈顶递增的。
• 当我们遍历的时候，遇到一个比栈顶柱子矮的柱子时，就可以确定栈顶柱子为右边界，从而计算以它为高度的矩形面积。

遍历柱子：

• 从左到右遍历每个柱子：
  • 如果当前遍历柱子比栈顶柱子高，直接压入栈。
  • 如果当前遍历柱子比栈顶柱子矮，说明当前栈顶柱子为右边界，可以计算以它为高度的矩形面积：
    • 高度就是栈顶柱子的高度。
    • 宽度是当前遍历柱子的索引减去栈顶柱子左边柱子的索引再减1。
    • 计算面积并更新最大面积。
    • 重复这个过程，直到当前柱子比栈顶柱子高，再把当前柱子压入栈。
• 遍历结束后，返回最大面积。

如果看完上面的过程，还是不够了解，可以看看下面的递推过程

为什么要在数组头部添加一个0呢？

比如说数组是[2,1]，那遍历到1的时候，栈顶索引是0，对应元素是2。将栈顶元素pop()弹出来之后，再peek()就报错了。为了减少边界条件的判断，可以再头部添加一个0，这样peek()的时候，不需要判断栈是否为空

为什么要在数组尾部添加一个0呢？

比如说数组是[1,2,3]，那其实每遍历一个元素都是直接压入栈中，这样永远不会有计算面积的时候。但是如果在数组后面添加一个0，遍历到这个0的时候，就会触发面积计算

public int largestRectangleArea(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(0);
    // 在原有数组的头、尾部添加0
    int[] heightArr = new int[heights.length + 2];
    for (int i = 0; i < heights.length; i++) {
        heightArr[i + 1] = heights[i];
    }
    int result = 0;
    for (int i = 0; i < heightArr.length; i++) {
        while (!stack.isEmpty() && heightArr[i] < heightArr[stack.peek()]) {
            // 弹出栈顶元素作为高度
            int height = heightArr[stack.pop()];
            // 计算宽度
            int temp = (i - stack.peek() - 1) * height;
            if (temp > result) {
                // 更新最大面积
                result = temp;
            }
        }
        stack.push(i);
    }
    return result;
}

双指针

【思路】

1. minLeftIndex 数组：
   1. 用于记录每个柱子左边第一个比它小的柱子的下标。
   2. 初始化时，minLeftIndex[0] = -1，表示第一个柱子左边没有更小的柱子。
   3. 对于每个柱子 i，通过 while 循环向左查找第一个比它小的柱子。注意，向左查找的时候，没有必要向左一个一个来遍历，可以借鉴前者的结论来帮助跳跃。
      • 由于heights[t] >= heights[i]，t左边的第一个比 heights[t] 矮柱子不一定比 heights[i] 矮。
      • 但是显然，那些比 heights[t] 高的柱子已经没必要遍历了，所以 t 可以直接跳到比 heights[i] 矮的柱子，即 t = minRightIndex[t]，而没有必要t–
2. minRightIndex 数组：
   1. 用于记录每个柱子右边第一个比它小的柱子的下标。
   2. 初始化时，minRightIndex[size - 1] = size，表示最后一个柱子右边没有更小的柱子。
   3. 对于每个柱子 i，通过 while 循环向右查找第一个比它小的柱子。
3. 计算最大矩形面积：
   1. 对于每个柱子 i，矩形的高度为 heights[i]，宽度为 (minRightIndex[i] - minLeftIndex[i] - 1)。
   2. 通过遍历所有柱子，计算每个矩形的面积，并更新最大值 result。

【时间复杂度】

• 每个柱子最多被访问两次（一次向左，一次向右），因此时间复杂度为 O(n)

【空间复杂度】

• 使用了两个辅助数组 minLeftIndex 和 minRightIndex，空间复杂度为 O(n)

public int largestRectangleArea(int[] heights) {
    int size = heights.length;
    // 记录每个柱子左边第一个小于该柱子的下标
    int[] minLeftIndex = new int[size];
    // 记录每个柱子右边第一个小于该柱子的下标
    int[] minRightIndex = new int[size];

    // 初始化 minLeftIndex
    minLeftIndex[0] = -1; // 第一个柱子左边没有更小的柱子
    for (int i = 1; i < size; i++) {
        // 即从柱子 i 的左边第一个柱子开始检查
        int t = i - 1;
        // 不断向左寻找第一个小于 heights[i] 的柱子
        while (t >= 0 && heights[t] >= heights[i]) {
            // 注意，由于heights[t] >= heights[i]，t左边的第一个比 heights[t] 矮柱子不一定比 heights[i] 矮。
            // 但是显然，那些比 heights[t] 高的柱子已经没必要遍历了，所以 t 可以直接跳到比 heights[i] 矮的柱子，即 t = minRightIndex[t]，而没有必要t--
            t = minLeftIndex[t];
        }
        // 如果 t==-1 ，说明没有比 minRightIndex[i] 矮的柱子
        minLeftIndex[i] = t;
    }

    // 初始化 minRightIndex
    minRightIndex[size - 1] = size; // 最后一个柱子右边没有更小的柱子
    for (int i = size - 2; i >= 0; i--) {
        int t = i + 1;
        // 不断向右寻找第一个小于 heights[i] 的柱子
        while (t < size && heights[t] >= heights[i]) {
            t = minRightIndex[t];
        }
        minRightIndex[i] = t;
    }

    // 计算最大矩形面积
    int result = 0;
    for (int i = 0; i < size; i++) {
        int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
        result = Math.max(sum, result);
    }

    return result;
}

原文地址：https://blog.csdn.net/laodanqiu/article/details/145124265

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！