# 单调栈的使用

# 42接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

示例 1:

img

输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 

# 1. 暴力法

暴力法的想法很简单,遍历每个柱子,

对于每个柱子,计算这个柱子上面可以存储的水量

当前柱子上可以储存的水量 ,取决于它左边的最高点和右边的最高点,这两个最高点中较低的那个就是当前柱子储存完水的高度

当前柱子上可以储存的水量 = {两个最高点中的较小者} - 当前柱子的高度

public int trap1(int[] height) {
    int ret = 0;
    for (int i = 0; i < height.length; i++) {
        // 往左遍历
        int left = i;
        // 左边的最高点
        int leftHeight = height[left];
        // 往右遍历
        int right = i;
        // 右边的最高点
        int rightHeight = height[right];
        // 依次往左遍历
        while (left >= 0){
            leftHeight = Math.max(leftHeight,height[left]);
            left--;
        }
        // 依次往右遍历
        while (right < height.length){
            rightHeight = Math.max(rightHeight,height[right]);
            right++;
        }
        ret += Math.min(leftHeight,rightHeight) - height[i];
    }
    return ret;
}

时间复杂度 O(n^2)

需要遍历每个柱子,对于每个柱子都要往左往右遍历一遍

AC: 7%

# 2. 空间换时间

在暴力法中,我们计算了每个柱子的左右两边的最高点

而主要的时间复杂度都浪费在了计算左右两边最高点的过程,我们可以用一个两个数组记录这些信息,从而省去每轮都要遍历的过程

// 2. 空间换时间
public int trap2(int[] height){
    if (height.length < 3){
        return 0;
    }
    int ret= 0;
    int[] leftMax = new int[height.length];
    int[] rightMax = new int[height.length];
    leftMax[0] = height[0];
    for (int i = 1;i<height.length;i++){
        height[i] = Math.max(height[i],leftMax[i-1]);
    }
    rightMax[height.length-1] = height[height.length-1];
    for (int j = height.length-2;j >= 0;j--){
        height[j] = Math.max(height[j],rightMax[j+1]);
    }
    for (int i = 0; i < height.length; i++) {
        ret += Math.min(leftMax[i],rightMax[i]) - height[i];
    }
    return ret;
}

时间复杂度:O(N)

执行用时:1 ms, 在所有 Java 提交中击败了99.79%的用户

内存消耗:37.9 MB, 在所有 Java 提交中击败了88.64%的用户

# 3. 优化的方法2

方法二在计算 leftMax 和 rightMax 数组的时候,需要遍历两边数组,最后计算的时候又需要遍历一遍,共需要遍历3遍

可以把这三次遍历操作放到一次遍历过程中。

思考方法2中更新leftMax 和 rightMax 数组的逻辑,:

  1. 当前leftMax只依赖于左边一个leftMax 和当前height
  2. 当前rightMax 只依赖于右边一个rightMax 和当前height
// 优化方法2
public int trap3(int[] height){
    if (height==null || height.length < 3){
        return 0;
    }
    int ret = 0;
    int left = 0;
    int right  = height.length-1;
    int leftHeightest = height[left];
    int rightHeightest = height[right];
    while (left < right){
        if (leftHeightest < rightHeightest){
            // 左边最高点更低, 水柱的最高点只需要考虑 leftHeightest 就行了
            left++;
            if (height[left] < leftHeightest){
                // 当前left位置可以被leftHeightest围住
                ret += leftHeightest - height[left];
            }else{
                leftHeightest = height[left];
            }
        }else{
            right--;
            if (height[right] < rightHeightest){
                ret += rightHeightest - height[right];
            }else{
                rightHeightest = height[right];
            }
        }
    }
    return ret;
}

时间复杂度:O(N)

执行用时:1 ms, 在所有 Java 提交中击败了99.79%的用户

内存消耗:38.3 MB, 在所有 Java 提交中击败了30.98%的用户

# 4:单调栈

模拟一下计算过程:

image-20201228141159178

image-20201228141225746

image-20201228141238428

image-20201228141300186

image-20201228141313220

image-20201228141327920

image-20201228141341243

image-20201228141421638

image-20201228141405005

image-20201228141446470

image-20201228141459161

image-20201228141511040

image-20201228141524518

// 4. 单调栈
public int trap4(int[] height){
    if (height==null || height.length < 3){
        return 0;
    }
    Deque<Integer> monoStack = new ArrayDeque<>();
    int ret = 0;
    for (int i = 0; i < height.length; i++) {
        while (!monoStack.isEmpty() && height[i] > height[monoStack.peek()]){
            // 如果当前柱子的高度,高于栈顶元素的高度
            // 那么当前柱子可以当作储水的区域的右边界
            int topIndex = monoStack.pop();
            // 寻找左边界,如果栈为空,则说明没有左边界,结束当前循环
            if (monoStack.isEmpty()){
                break;
            }
            ret += (i - monoStack.peek() -1) * (Math.min(height[i],height[monoStack.peek()]) - height[topIndex]);
        }
        // 每个元素的下标都需要入栈一次
        monoStack.push(i);
    }
    return ret;
}

执行用时:2 ms, 在所有 Java 提交中击败了49.07%的用户

内存消耗:37.9 MB, 在所有 Java 提交中击败了81.23%的用户

# 84柱状图中的最大矩形

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积,其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3]
输出: 10

# 1. 暴力

暴力法思路很简单:对于每个位置,往左往右找到比它高的柱子,组成矩形

// 矩形面积 = 宽 x 高
// 1. 暴力解法:每次固定「高」,获得最大的宽
public int largestRectangleArea(int[] heights) {
    int maxArea = 0;
    for (int i = 0;i<heights.length;i++){
        int left = i;
        int right = i;
        while (left-1 >= 0 && heights[left-1] >= heights[i]){
            left--;
        }
        while (right+1 < heights.length && heights[right+1] >= heights[i]){
            right++;
        }
        maxArea = Math.max(maxArea,(right-left+1)*heights[i]);
    }
    return maxArea;
}

# 2. 单调栈

参考接雨水的思考过程:

栈中存储单调递增的柱子,遇到比栈顶矮的柱子,则计算栈中柱子组成的矩形

// 2. 优化:空间换时间
// 用栈:栈中存储暂时还无法确定能延伸出来的最大矩形的位置
public int largestRectangleArea2(int[] heights) {
    int[] tmp = new int[heights.length + 2];
    System.arraycopy(heights, 0, tmp, 1, heights.length);

    int maxArea = 0;
    Deque<Integer> stack = new LinkedList<>();
    for (int i = 0; i < tmp.length; i++) {
        while (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]){
            // 当前栈顶索引,也就是需要计算的位置
            int highIndex = stack.pop();
            maxArea = Math.max(maxArea,tmp[highIndex] * (i-stack.peek()-1));
        }
        stack.push(i);
    }
    return maxArea;
}

# 85最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。

示例 1:

输入:matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出:6 解释:最大矩形如上图所示。 示例 2:

输入:matrix = [] 输出:0 示例 3:

输入:matrix = [["0"]] 输出:0

# 1. 暴力解法

遍历每个元素,计算以当前元素作为右下角的矩形的面积,取最大值

矩形面积 = 长 x 宽

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0){
            return 0;
        }
        // 记录每个元素左边的连续的1的个数
        int[][] width = new int[matrix.length][matrix[0].length];
        int ret = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0;j < matrix[0].length;j++){
                // 计算每个元素左边的连续的1的个数
                if (matrix[i][j] == '0'){
                    // 如果当前元素是 0 ,那打扰了
                    width[i][j] = 0;
                }else {
                    // 如果j不在最左边,则为左边的width+1,否则就是1
                    width[i][j] = j>0 ? width[i][j-1]+1 : 1;
                    int curHeight = 0;
                    int curWidth = width[i][j];
                    for (int k = i;k >= 0;k--){
                        // 依次向上遍历
                        curHeight++;
                        curWidth = Math.min(curWidth,width[k][j]);
                        ret = Math.max(ret,curHeight*curWidth);
                    }
                }
            }
        }
        return ret;
    }
}

执行用时:25 ms, 在所有 Java 提交中击败了5.48%的用户

内存消耗:41.7 MB, 在所有 Java 提交中击败了50.01%的用户

# 2. 单调栈

利用84题计算最大矩形面积的函数

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0){
            return 0;
        }
        int []height = new int[matrix[0].length];
        int maxArea = 0;
        for (int i = 0;i < matrix.length;i++){
            for (int j = 0;j < matrix[0].length;j++){
                if (matrix[i][j] == '1'){
                    height[j] += 1;
                }else {
                    height[j] = 0;
                }
            }
            maxArea = Math.max(maxArea,largestRectangleArea(height));
        }
        return maxArea;
    }
    public int largestRectangleArea(int[] heights) {
        int[] tmp = new int[heights.length + 2];
        System.arraycopy(heights, 0, tmp, 1, heights.length);

        int maxArea = 0;
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < tmp.length; i++) {
            while (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]){
                // 当前栈顶索引,也就是需要计算的位置
                int highIndex = stack.pop();
                maxArea = Math.max(maxArea,tmp[highIndex] * (i-stack.peek()-1));
            }
            stack.push(i);
        }
        return maxArea;
    }
}

执行用时:5 ms, 在所有 Java 提交中击败了91.03%的用户

内存消耗:42.1 MB, 在所有 Java 提交中击败了9.79%的用户

# 316去除重复字母

# 1. 单调栈

依次遍历每个字母,如果还不确定保留与否,也不能决定它前面的字母的去留,就先入栈。

如果当前字母小于栈顶字母,并且栈顶字母在后面还会出现,那说明栈顶元素可以舍弃了。

class Solution {
    public String removeDuplicateLetters(String s) {
        if (s == null || s.length() == 0){
            return s;
        }
        // 存储每个元素还有多少个没用
        int[] charNums = new int[26];
        // 储存栈中有没有某个元素
        boolean[] charExist = new boolean[26];
        Deque<Character> stack = new ArrayDeque<>();
        for (Character c : s.toCharArray()){
            charNums[c-'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            Character cur = s.charAt(i);
            // 如果栈中存在当前元素,肯定保留栈中的元素,舍弃当前元素
            if (charExist[cur-'a']){
                charNums[cur-'a']--;
                continue;
            }
            // 如果栈顶元素大于 当前元素,并且栈顶元素还会在后面出现,则舍弃栈顶元素
            while (!stack.isEmpty() && cur < stack.peek() && charNums[stack.peek()-'a'] > 0){
                // 如果当前元素小于栈顶,并且栈顶元素还没有用完,说明栈顶元素需要被替换
                Character top = stack.pop();
                charExist[top-'a'] = false;
            }
            stack.push(cur);
            charNums[cur-'a']--;
            charExist[cur-'a']=true;
        }
        StringBuilder stringBuilder = new StringBuilder();
        while (!stack.isEmpty()){
            stringBuilder.append(stack.pop());
        }
        stringBuilder.reverse();
        return stringBuilder.toString();
    }
}

执行用时:6 ms, 在所有 Java 提交中击败了27.92%的用户

内存消耗:38.4 MB, 在所有 Java 提交中击败了50.11%的用户

# 402移掉K位数字

# 1. 单调栈

依次遍历每个数字,如果当前数字比栈顶数字小,并且已经删掉的数字数目 < k(还有删的余地)则把栈顶元素删掉

特别地,为了统一对最后一个元素的操作,可以加一个哨兵:在num后面加一个比0的ASCII码还小的元素,比如 "."

class Solution {
    public String removeKdigits(String num, int k) {
        num = num + ".";
        int removed = 0;
        StringBuilder stack = new StringBuilder();
        for (int i = 0;i<num.length();i++){
            Character cur = num.charAt(i);
            while (stack.length()!=0 && stack.charAt(stack.length()-1) > cur){
                if (removed >= k){
                    break;
                }
                stack.deleteCharAt(stack.length()-1);
                removed++;
            }
            stack.append(cur);
        }
        // 删除结尾的.
        stack.deleteCharAt(stack.length()-1);
        // 删除开头的 0
        while (stack.length() > 0 && stack.charAt(0) == '0'){
            stack.deleteCharAt(0);
        }
        if (stack.length() == 0){
            return "0";
        }
        return stack.toString();
    }
}

执行用时:14 ms, 在所有 Java 提交中击败了24.33%的用户

内存消耗:39 MB, 在所有 Java 提交中击败了26.86%的用户

# 496下一个更大元素

# 1. 暴力法

对于 nums1 中的每个元素,计算它在 nums2 中的写一个更大元素

class Solution {
    private int nextElement(int[] nums2,int n){
        // 初始情况,设为-2,意味还没遇到和它相等的元素
        int ret = -2;
        for (int i = 0;i < nums2.length;i++){
            if (nums2[i] == n){
                // 遇到了和它相等的元素
                ret = -1;
            }
            if (ret == -1 && nums2[i] > n){
                // 如果已经遇到了和它相等的元素,并且当前元素大于n
                ret = nums2[i];
                break;
            }
        }
        return ret < 0 ? -1:ret;
    }
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] ret = new int[nums1.length];
        for (int i = 0;i < ret.length;i++){
            ret[i] = nextElement(nums2,nums1[i]);
        }
        return ret;
    }
}

执行用时:8 ms, 在所有 Java 提交中击败了17.27%的用户

内存消耗:38.4 MB, 在所有 Java 提交中击败了93.11%的用户

# 2. 单调栈

不管三七二十一,先把nums2中所有元素的写一个较大元素求出来,放到哈希表中

然后 nums1中的每个元素去哈希表中查结果

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer,Integer> results = new HashMap<>();
        // 原始值为-1
        for (int i = 0;i < nums2.length;i++){
            results.put(nums2[i],-1);
        }
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0;i < nums2.length;i++){
            int cur = nums2[i];
            while (!stack.isEmpty() && stack.peek() < cur){
                // 如果栈顶元素 小于 当前元素,那还等什么,栈顶元素的下一个较大元素就是当前元素
                int top = stack.pop();
                results.put(top,cur);
            }
            stack.push(cur);
        }
        int[] ret = new int[nums1.length];
        for (int i = 0;i<ret.length;i++){
            ret[i] = results.get(nums1[i]);
        }
        return ret;
    }
}

# 581最短无序连续子数组

# 739每日温度

# 901股票价格跨度

Last Updated: 1/16/2021, 9:27:12 AM