代码随想录 | 单调栈part01 part02 part03

739 每日温度

单调栈，用于快速检索某个元素左边或者右边第一个比它大或者小的元素
通过维持一个有序的栈来实现
寻找比它大的，则栈顶到栈底是递增的，反之则是递减的

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res = [0]*len(temperatures)
        stack = [0]
        for i in range(len(temperatures)):
            while len(stack) != 0 and temperatures[i] > temperatures[stack[-1]]:
                res[stack[-1]] = i - stack[-1]
                stack.pop()
            stack.append(i)
        return res
1
2
3
4
5
6
7
8
9
10

496 下一个更大元素I

使用上一题的思路，嵌入一个On的index，并使用try捕捉异常

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []
        res = [-1]*len(nums1)
        for i in range(len(nums2)):
            while len(stack) > 0 and nums2[stack[-1]] < nums2[i]:
                try:
                    index = nums1.index(nums2[stack[-1]])
                    res[index] = nums2[i]
                    stack.pop()
                except:
                    stack.pop()
            stack.append(i)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

看解答意识到还可以用dic进一步优化

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []
        res = [-1]*len(nums1)
        dic = {}
        for i in range(len(nums1)):
            dic[nums1[i]] = i
        for i in range(len(nums2)):
            while len(stack) > 0 and nums2[stack[-1]] < nums2[i]:
                if nums2[stack[-1]] in dic:
                    index = dic[nums2[stack[-1]]]
                    res[index] = nums2[i]
                stack.pop()
            stack.append(i)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

503 下一个更大元素II

有两个思路，第一个是数组倍增两个连起来，模拟向前寻找的过程，但是需要注意储存结果时的下标

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        res = [-1]*len(nums)
        stack = []
        nums2 = nums+nums
        length = len(nums)
        for i in range(len(nums2)):
            # print(nums2[i],stack)
            while len(stack) != 0 and nums2[stack[-1]] < nums2[i]:
                if stack[-1] < length:
                    res[stack[-1]] = nums2[i]
                else:
                    res[stack[-1]-length] = nums2[i]
                stack.pop() 
            stack.append(i)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

另外一个思路是从左向右扫一遍，再从右向左扫一遍，然后结果合并

42 接雨水

确实有难度，需要仔细分析单调栈的三种情况才行

class Solution:
    def trap(self, height: List[int]) -> int:
        res = 0
        stack = [0]
        for i in range(1,len(height)):
            if height[i] < height[stack[-1]]:
                stack.append(i)
            elif height[i] == height[stack[-1]]:
                stack.pop()
                stack.append(i)
            else:
                while len(stack)>0 and height[stack[-1]] < height[i]:
                    rH = height[i]
                    cH = height[stack[-1]]
                    stack.pop()
                    if len(stack) != 0:
                        lH = height[stack[-1]]
                        res += (min(rH,lH) - cH)*(i-stack[-1]-1)
                stack.append(i)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

84 柱状图中最大的矩形

实际上是找左右两边第一个比它小的元素，据此确定宽度，以自己高度为高计算面积
暴力遍历？超时了。。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        res = -1
        heights = [-1]+heights+[-1]
        for i in range(1,len(heights)-1):
            left = i-1
            while left >= 0 and heights[left] >= heights[i]:
                left -= 1
            right = i+1
            while right<len(heights) and heights[right] >= heights[i]:
                right += 1
            w = right - left - 1
            res = max(res,heights[i]*w)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

还是得用单调栈，看了解答意识到，上一题是在找每个元素左右比它大的第一个元素，本题是在找每个元素左右比它小的第一个元素

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = [0]
        res = 0
        heights = [-1]+heights+[-1]
        for i in range(1,len(heights)):
            if heights[i] == heights[stack[-1]]:
                stack.pop()
                stack.append(i)
            elif heights[i] > heights[stack[-1]]:
                stack.append(i)
            else:
                while stack and heights[i] < heights[stack[-1]]:
                    mid = stack[-1]
                    stack.pop()
                    if stack:
                        left = stack[-1]
                        right = i
                        res = max(res,heights[mid]*(right-left-1))
                stack.append(i)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

注意，这里首尾两根柱子也可以用于计算最大面积，和接雨水有区别，因此需要在首尾添加元素保证边界不会出现在首尾柱子上