单调栈II： leetcode 581、901、42、84

leetcode 581：最短无序连续子数组

题目描述：
给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

示例 1：
输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

示例 2：
输入：nums = [1,2,3,4]
输出：0

示例 3：
输入：nums = [1]
输出：0

提示：
1 <= nums.length <= 104
-105 <= nums[i] <= 105

思路1： 排序
本题是要找到不满足升序部分的数组的长度，所以可以对数列进行排序，排序后对比就可以知道所求的长度。

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        nums_s = sorted(nums)
        res = []
        for i in range(len(nums)):
            if nums_s[i] != nums[i]:
                res.append(i) 
        return max(res) - min(res) + 1 if res else 0
1
2
3
4
5
6
7
8

思路2：
因为求得是不满足单调性的长度，所以想到用单调栈求出不满足单调的位置，就可以求出来长度。
这里需要注意的是，我们可以观察到数组是这样分布的【单调上升，所求部分，单调上升】所以我们需要求两部分的临界点，采用了两次单调栈的想法，一个单调递增栈求左边边界，单调递减栈求右边边界。分别是从左右两边开始遍历的；这里需要注意的是，只用一次单调栈是无法求出两个边界的，因为栈的增减是确定的，只能求出一个；

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        key_1, key_2 = len(nums), 0
        stack = []
        for i in range(len(nums)):
            while stack and nums[i] < nums[stack[-1]]:
                peek = stack.pop()
                key_1 = min(key_1, peek)
            stack.append(i)

        stack = []
        for j in range(len(nums)-1, -1, -1):
            while stack and nums[j] > nums[stack[-1]]:
                peek = stack.pop()
                key_2 = max(key_2, peek)
            stack.append(j)
        return max(key_2-key_1+1, 0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

思路3： 双指针
主要参考的题解链接
有一点绕，但是相对好理解。

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n=len(nums)
        if n==1:
            return 0
        minn=nums[n-1]
        maxn=nums[0]
        right=left=0
        for j in range(n): # 从左侧更新它的最大值
            if nums[j]<maxn:
                right=j # right 是最后一个比前面所有值最大值小的位置
            maxn=max(maxn,nums[j])
        for j in range(n-1,-1,-1): #从右侧更新它的最小值
            if nums[j]>minn:
                left=j
            minn=min(minn,nums[j])
        # left和right分别是中间部分的左右边界
        if right==left:
            return 0
        return right-left+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

leetcode 901：股票价格跨度

题目描述：
编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。

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

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

示例：
输入：[“StockSpanner”,“next”,“next”,“next”,“next”,“next”,“next”,“next”], [[],[100],[80],[60],[70],[60],[75],[85]]
输出：[null,1,1,1,2,1,4,6]
解释：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75) 被调用并返回 4，
S.next(85) 被调用并返回 6。

注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
(包括今天的价格 75) 小于或等于今天的价格。

提示：
调用 StockSpanner.next(int price) 时，将有 1 <= price <= 10^5。
每个测试用例最多可以调用 10000 次 StockSpanner.next。
在所有测试用例中，最多调用 150000 次 StockSpanner.next。
此问题的总时间限制减少了 50%。
通过次数25,882提交次数46,142

思路： 求比当天小的连续天数，想到单调栈
在本题中单调栈中存放两个值（股票价格，比这天小的连续天数）

class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        k = 1
        while self.stack and self.stack[-1][0] <= price:
            k += self.stack[-1][1]
            self.stack.pop()
        self.stack.append((price, k))
        return k
        
# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

leetcode 42： 接雨水

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

示例 1：

输入：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 个单位的雨水（蓝色部分表示雨水）。

示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

提示：
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

解本题主要参考的题解链接
思路1：
分析可以接水的条件，就是知道当前位置的左右高度最大值，然后利用这个最大值减去自己的高度就是自己这个位置可以接到的水量。

class Solution:
    def trap(self, height: List[int]) -> int:
        # 超时
        res = 0
        for i in range(1, len(height)-1):
            max_z, maxy = 0, 0
            for z in range(0, i):
                max_z = max(max_z, height[z])
            for y in range(i+1, len(height), 1):
                maxy = max(maxy, height[y])
            res += max(min(max_z, maxy) - height[i], 0)
        return res
1
2
3
4
5
6
7
8
9
10
11
12

这样做会超时，进而引出使用动态规划的方式保存最大值，避免反复的搜索两边的最大值，一次搜索保存所有位置左右两侧的最大值。
思路2： 动态规划记录两侧最大值

    def trap2(self, height: List[int]) -> int:
        res = 0
        dp_z, dp_y = [0] * len(height), [0]*len(height)
        for i in range(1, len(height)):
            dp_z[i] = max(dp_z[i-1], height[i-1])
        for j in range(len(height)-2, 0, -1):
            dp_y[j] = max(dp_y[j+1], height[j+1])
        # print(dp_z, dp_y)
        for k in range(1, len(height)-1):
            res += max(min(dp_z[k], dp_y[k])-height[k], 0)
        return res
1
2
3
4
5
6
7
8
9
10
11

思路3： 单调栈，分析一处的水量需要等到下一个比他高的位置出现才可以计算，这里参考的题解链接。
单调栈是一个递减栈，遇到一个比栈顶 cur大的 r ，就开始计算，高度是 r 和 cur的下一个元素 l 的较小值（因为左边也就是下一个元素是比cur大的）-cur的高度，宽度是 r-l-1，就是这段有多长。

    def trap3(self, height: List[int]) -> int:
        # 单调栈
        stack = []
        res = 0
        for i in range(0, len(height)):
            while stack and height[stack[-1]] < height[i]:
                cur = stack.pop()
                if not stack:
                    break
                l = stack[-1]
                res += ((i - l - 1) * (min(height[i], height[l]) - height[cur]))
            stack.append(i)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13

思路4： 双指针

leetcode 84：柱状图中最大的矩形

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

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

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

提示：
1 <= heights.length <=105
0 <= heights[i] <= 104

思路： 单调栈
这题和42题接雨水很像，都是遇到下一个更高的矩形，才知道当前的高度可以得到的矩形的面积；所以想到使用单调栈；
主要参考的题解链接
42和84是单调栈的常出题目
这里需要注意的一点就是要为数组在左右两边加上一个0，因为有些情况如果不加上两个哨兵点的话输出是不对的。
比如：[1, 2, 3]这样递增的栈没有遇到弹栈的情况，就无法得到一个结果，所以在后面加一个0；再比如[2, 1, 2]在右边添加了一个0之后变成[2, 1, 2, 0]，栈的变化是[2]-[1]-[1, 2]-[1]-这是1和0进行比较，0小于1，对1进行弹栈，但是1可以确定的宽度不是2，而是3，造成这种错误的原因是之前弹出了第一个2但是我们却没有记忆，所以在最开始放置一个0，这样每次我们就去cur元素左边元素+1的位置就是要计算的宽度了，具体的见代码：

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        maxx = 0
        stack = []
        heights = [0] + heights
        heights.append(0)
        for i in range(len(heights)):
            while stack and heights[stack[-1]] > heights[i]:
                peek = stack.pop()
                left = stack[-1]
                maxx = max(maxx, (i - left - 1) * heights[peek])
            stack.append(i)
        return maxx
1
2
3
4
5
6
7
8
9
10
11
12
13