力扣题目汇总分析 利用单调栈解决问题

496 下一个更大元素 I

问题

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。为nums1中每个数字 x找到下一个更大元素。如果不存在下一个更大元素，那么本次查询的答案是 -1

示例 1：

输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：

• 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
• 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
• 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

分析

可以暴力法通过两层循环来实现，但是会超时。
使用暴力法，我们需要为nums1中每个元素 遍历nums2找到对应位置然后继续遍历确定下一个最大元素。
可不可以不遍历nums2，直接访问哈希表得到下一个最大元素呢？让哈希表的key是nums2中的每个元素值，value就是key对应的nums2中的下一个最大元素！
使用单调栈来构建这个哈希表！
找右侧（下一个）最大元素，从右往左遍历nums2，找右边出现的第一个大的元素，所以所有新元素都要入栈，然后构建出一个从下往上（从左往右）看单调递减的栈。
示例1，
倒数第一个元素2，栈空，记录d[4]=-1，把2入栈；【栈：2】
倒数第二个元素4，4大于栈顶元素2，弹出2，栈空，记录d[3]=-1，把4入栈；【栈：4】
倒数第三个元素3，3小于栈顶元素4，记录d[1]=4，把3入栈，满足单调递减；【栈：4，3】
倒数最后一个元素1，1小于栈顶元素3，记录d[0]=3，把1入栈，满足单调递减。【栈：4，3，1】

代码实现

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        //key:nums2中每个不重复的元素 value:每个元素对应的下一个最大元素
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        Stack<Integer> stack=new Stack<Integer>();
        int[] l=new int[nums1.length];
        for (int i=nums2.length-1;i>=0;i--){
            while (!stack.empty()&&stack.peek()<=nums2[i]){
                stack.pop();
            }
            if (stack.empty()){
                map.put(nums2[i],-1);
            }else{
                map.put(nums2[i],stack.peek());
            }
            stack.push(nums2[i]);
        }
        for (int i=0;i<nums1.length;i++){
            l[i]=map.get(nums1[i]);
        }
        return l;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

901 股票价格跨度

问题

设计一个算法收集某些股票的每日报价，并返回该股票当日价格的 跨度 。

当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

例如，如果未来 7 天股票的价格是 [100,80,60,70,60,75,85]，那么股票跨度将是 [1,1,1,2,1,4,6] 。

实现 StockSpanner 类：

StockSpanner() 初始化类对象。
int next(int price) 给出今天的股价 price ，返回该股票当日价格的 跨度 。

示例：

输入：
[“StockSpanner”, “next”, “next”, “next”, “next”, “next”, “next”, “next”]
[[], [100], [80], [60], [70], [60], [75], [85]]
输出：
[null, 1, 1, 1, 2, 1, 4, 6]

解释：
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // 返回 1
stockSpanner.next(80); // 返回 1
stockSpanner.next(60); // 返回 1
stockSpanner.next(70); // 返回 2
stockSpanner.next(60); // 返回 1
stockSpanner.next(75); // 返回 4 ，因为截至今天的最后 4 个股价 (包括今天的股价 75) 都小于或等于今天的股价。
stockSpanner.next(85); // 返回 6

分析

和前一个题目思路一样，有两点不同

1. 只是这相当于找前一个更大元素，力扣内部机制就是从左往右输入每日price，符合！（如果是前一题那种有个nums2，那么我们从左到右遍历nums2，来为每个数组元素找到前一个更大元素）
2. 返回更大元素和当前元素之间的跨度，且是依次调用next方法找到前一个更大元素，所以不需要哈希表来存值。每次入栈的除了元素值（用来比较栈顶和即将入栈元素，构建单调递减元素）还有元素index（为了求跨度），声明一个Stack<int[]> stack，此外我们在类里面定义一个成员变量来记录index的增加。

代码实现

class StockSpanner {
    Stack<int[]> stack;
    int numSum;
    
    public StockSpanner() {
        this.stack=new Stack<int[]>();
        this.numSum=0;
    }
    
    public int next(int price) {
        this.numSum+=1;
        //一个对象实例第一次调用next，栈空时的处理
        if (this.stack.empty()){
            this.stack.push(new int[]{numSum,price});
            return this.numSum;
        }
        //值更小的栈顶就丢掉
        while ((!this.stack.empty())&&(this.stack.peek()[1]<=price)){
            this.stack.pop();
        }
        int span;
        if (this.stack.empty()){
            span=this.numSum;
        }else{
            span=this.numSum-this.stack.peek()[0];
        }
        //总之新元素都要入栈
        this.stack.push(new int[]{numSum,price});
        return span;
    
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

84 柱状图中的最大矩形

问题

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

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

分析

暴力法，枚举矩形的宽度，也就是搞个二层循环，起始索引i 和结束索引j ，然后高就是i,j之间最矮的那个柱子的高度。还可以枚举矩形的高度，因为可以发现矩形的高总是某个柱子的高度，枚举每个柱子高度，以该高度heights[i]作为最终矩形的高度，然后以i往左往右扩展找到柱子高度小于heights[i]的柱子，确定宽。但是这两种方法力扣上面会超时。

枚举高，我们需要为每个柱子的高度找到围成这一高度最大面积矩形的左右边界，最坏情况下遍历了n，有没有一种可能遍历高，利用单调栈来找。

因为我们是往左往右扩展找到柱子高度小于heights[i]的柱子，找前一个和下一个更小元素。如果建立一个单调递增栈，那前一个更小元素自然有了，下一个更大元素就看新来的高度，如果新来的高度小于我，那我就找到了以我为高度勾勒出的最大矩形面积，如果新来的高度大于我，那就先入栈，满足单调递增。当所有元素遍历完经历了入栈出栈等操作，栈里面剩下的都是从当前高度往后可以一直画矩形的，因为高度都大于当前高度！懂了懂了么~

显然这是找跨度，所以栈里存索引，定义一个变量maxArea保存最大面积，分析示例1：
i=0准备入栈，栈空，入栈；【栈：0】
i=1准备入栈，发现栈顶值对应柱子高度>将入栈值对应柱子高度，于是得到以2为高度勾勒的矩形最大也就area=2*1，比较maxArea看是否替换，栈顶出栈，i=1入栈；【栈：1】
i=2准备入栈，发现栈顶值对应柱子高度<将入栈值对应柱子高度，i=2入栈；【栈：1，2】
i=3准备入栈，发现栈顶值对应柱子高度<将入栈值对应柱子高度，i=3入栈；【栈：1，2，3】
i=4准备入栈，发现栈顶值对应柱子高度>将入栈值对应柱子高度，于是得到以6为高度勾勒的矩形最大也就area=6*1，比较maxArea看是否替换，栈顶出栈，继续对比！栈顶值对应柱子高度<将入栈值对应柱子高度，于是得到以6为高度勾勒的矩形最大也就area=6*(4-2)，比较maxArea看是否替换，栈顶出栈，继续对比！发现栈顶值对应柱子高度<将入栈值对应柱子高度，i=4入栈；【栈：1，4】
i=5准备入栈，发现栈顶值对应柱子高度<将入栈值对应柱子高度，i=5入栈；【栈：1，4，5】

欧克！到这里遍历柱子高度完成，栈里面剩下的都是从当前高度往后可以一直画矩形的！

切忌！ 呜呜，我拿示例1分析，弄错了一个地方，当遇到栈顶值对应柱子高度>将入栈值对应柱子高度，准备计算area时，千万先要先弹出栈顶元素再计算area，因为存在如下图的情况，假如此时【栈：1，5】，i=2为栈顶，heights[i]=5，栈顶值对应柱子高度>将入栈值对应柱子高度，应该先弹出可以求出以5为高度勾勒的矩形最大area=5*(3-0-1)=10

代码实现

class Solution {
    public int largestRectangleArea(int[] heights) {
        //需要一个栈，存索引
        Stack<Integer> stack=new Stack<Integer>();
        //需要一个变量存最大矩形面积
        int maxArea=-1;
        int tmp;
        int area;
        for (int i=0;i<heights.length;i++){
            while (!stack.empty()&&heights[stack.peek()]>heights[i]){
                //先出栈
                tmp=stack.pop();
                if (!stack.empty()){
                    //i-stack.peek()-1 还要减去1
                    area=heights[tmp]*(i-stack.peek()-1);
                }else{
                    area=heights[tmp]*(i-(-1)-1);
                }
                maxArea=area>maxArea?area:maxArea;
            }
            stack.push(i);
        }
        while (!stack.empty()){
            tmp=stack.pop();
            if (!stack.empty()){
                area=heights[tmp]*(heights.length-stack.peek()-1);
            }else{
                area=heights[tmp]*(heights.length-(-1)-1);
            }
            maxArea=area>maxArea?area:maxArea;
        }
        return maxArea;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

42 接雨水

问题

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

分析

和上一个题目很像，我们来试试利用单调栈解决。
这个问题是求接水量，什么情况下会接住水，左右两边都有比我高的柱子，接多少水？左右两边分别找到最高的柱子，取矮的那个高度减去我自己的高度，就是我的接水量。
怎么找到左边两边最高的柱子呢？
法一：好像可以利用空间利用动态规划思想，当前柱子i的左边最高柱子等于max(柱子i-1的左边最高柱子 , 柱子i-1的高度)。右边同样。
法二：栈能否帮我们解决？这题与前面不一样，不是找前一个/后一个更大元素，是找最大元素！

xxx（学完括号匹配，再来续写单调栈的解决！

代码实现

class Solution {
    public int trap(int[] height) {
        //法一
        int sum=0;
        int n=height.length;
        int[] max_left=new int[n];
        int[] max_right=new int[n];
        for (int i=1;i<n-1;i++){
            max_left[i]=Math.max(max_left[i-1],height[i-1]);
        }
        for (int i=n-2;i>0;i--){
            max_right[i]=Math.max(max_right[i+1],height[i+1]);
        }
        //现在已经得到每列的左右两边最高的柱子高度
        //然后来求每列的接水量
        for (int i=1;i<n-1;i++){
            int m=Math.min(max_left[i],max_right[i]);
            if (m>height[i]){
                sum=sum+m-height[i];
            }
        }
        return sum;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22