image-20240305152647958

单调栈

通常针对一维数组的问题，如果需要寻找一个元素右边或者左边第一个比自己大或者小的元素的位置，就可以使用单调栈，时间复杂度为O(n)

单调栈的本质是空间换时间， 遍历的过程中需要使用一个栈记录右边第一个比当前元素高的值。优点是整个数组只需要遍历一次。

使用单调栈需要明确的几点：

  • 单调栈中存放的元素是什么？
  • 单调栈里的元素是递增还是递减？

单调栈中的元素可以是递增的也可以是递减的，具体需要看题目的需求。

单调栈中存放的元素最好是下标，这样具有更好的泛型

练习题

739、每日温度

image-20231212134352911

使用单调栈的方式从前往后进行遍历；

栈中的元素从栈底到栈顶对应下标的值是递减的，直到找到一个比栈顶元素大的值，然后出栈。

栈中存放的是元素的下标，如果出现一个新的元素比栈中元素都要大的时候，就对栈中元素进行循环遍历，将其对应的res值修改为当前元素的下标和栈中存放的值的差值，这就是最终结果，到最后一个元素的时候，因为初始化结果列表中元素值都是0，故不需要进行修改。

初始化答案res为全0的列表，这样可以防止后面的元素没有下一个更大的元素，当然这一点要根据题目的要求来，因为有些题目会赋值为-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res = [0] * len(temperatures)
        st = []
        # 从前往后进行遍历
        for index, temp in enumerate(temperatures):
            # st不为空且温度大于栈顶元素
            while st and temperatures[st[-1]] < temp:
                j = st.pop()
                # 题目中问的是下一个更高温度出现在几天之后 因此用下标之差表示即可
                res[j] = index - j
            st.append(index)
        return res

image-20231212135345977

image-20240121131154516

496、下一个更大元素I

image-20240105151441966

直接寻找

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = [-1]*len(nums1)
        # 寻找下一个更大的元素
        for index,n1 in enumerate(nums1):
            startindex = nums2.index(n1)
            for n in nums2[startindex+1:]:
                if n>n1:
                    res[index] = n
                    break
        return res

使用单调栈

题目中有【需要寻找最近一个比其大的元素】 这样的字眼，就可以使用 【单调栈】

本题需要注意的是题目中存在两个数组，寻找第一个数组在第二个数组元素中下一个比对应元素大的元素。题目中说了两个数组中是没有重复元素的，可以采用单调栈+哈希表的方式进行解决。

单调栈解决的是nums2中每个元素对应的下一个比其大的元素

哈希表解决的是用来存储每个元素对应的下一个元素值，这样方便对nums1进行遍历时的查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        st = []
        res = [-1]*len(nums2)
        for index,num in enumerate(nums2):
            # print(index,num)
            while st and nums2[st[-1]]<num:
                j = st.pop()
                res[j] = num
            st.append(index)
        # 使用zip通过两个可迭代的对象构造字典
        myhash = dict(zip(nums2,res))
        ans = []
        for n1 in nums1:
            ans.append(myhash[n1])
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        myhash = {}
        st = []
        res = []
        for index, n in enumerate(nums2):
            while st and nums2[st[-1]] < n:
                myhash[nums2[st.pop()]] = n
            st.append(index)
        for n1 in nums1:
            res.append(myhash.get(n1, -1))
        return res

image-20240120143638324

503、下一个更大元素II

image-20240120143718794

image-20240120143729232

出现这种需要循环才能判断的情况，可以采用求余数的方法来多遍历一次。

类似的思路还有打家劫舍II中头尾不能同时偷的情况，就可以采用将数组（列表）进行拆分：0-n-1和1-n的情况

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        # 如何解决循环的问题？
        # 循环也就最多循环一轮到自己本身
        # 用求余来表示
        res = [-1] * len(nums)
        st = []
        for index, n in enumerate(nums * 2):
            while st and nums[st[-1]] < n:
                res[st.pop()] = n
            st.append(index % len(nums))
        return res

image-20240120144607613

42、接雨水

image-20240120145358564

image-20240120145411157

在做本题之前，需要明确计算的方法是按照行进行计算还是按照列进行计算，这两个计算方法的不同会导致不同的做法。

按照行去计算的做法如下所示：逐行进行累加

42.接雨水2

按照列去计算的做法如下所示：逐列进行累加

42.接雨水1

按照列去计算的时候可以假设每一列的宽度为1，只需要逐列去进行累加即可得到最终结果，这个思路也衍生了下面的暴力算法：

  • 暴力算法【逐列累加】

暴力算法的思路是一列一列的去记录能够装的雨水是多少，最终累加起来。

记录每个节点左边和右边的最大高度，然后用两个最大高度中的最小值减去当前高度，然后乘以宽度1，将这个值累加到res中。

1
s = (min(lHeight,rHeight)-height[i]) * 1

当遍历到第一个柱子和最后一个柱子的时候，不需要计算面积。对于其余的柱子，需要寻找其左边和右边的最高的柱子，然后取两者中的最小值，用最小值的高度减去height[i]，得到差值就是可以装的雨水的高度，然后用这个高度再乘以宽度1，就是能装的雨水的体积。最后一直累加这个和，得到能装的最多的雨水。

1
2
3
4
5
6
7
lHeight = height[i]
rHeight = height[i]
for j in range(i + 1, len(height)):
    rHeight = max(rHeight, height[j])
for j in range(i - 1, -1, -1):
    lHeight = max(lHeight, height[j])
res += min(lHeight, rHeight) - height[i]

很不幸代码超时了。

image-20240120200838854

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def trap(self, height: List[int]) -> int:
        # 暴力算法（从前往后进行遍历）记录当前位置左右的最高点
        res = 0
        for i in range(1, len(height) - 1):
            lHeight = height[i]
            rHeight = height[i]
            for j in range(i + 1, len(height)):
                rHeight = max(rHeight, height[j])
            for j in range(i - 1, -1, -1):
                lHeight = max(lHeight, height[j])
            res += min(lHeight, rHeight) - height[i]
            # print(i,lHeight,rHeight   
            res += min(lHeight, rHeight) - height[i]
        return res

  • 双指针【逐列累加】

在暴力算法中，每轮循环都需要重复去寻找当前位置左右更高的高度，可以采用双指针的方法进行优化：

注意：双指针方法和暴力算法本质上都是逐列进行累加的。

通过两个单独的for循环，得到lHeight和rHeight数组（分别表示每个柱子左右两侧的最高的高度是多少），然后在通过一次循环，从1遍历到n-2位置的柱子，然后累加最终能够装的雨水的体积。

这里需要注意在循环的时候，需要进行赋初始值，例如找左侧最大值的时候，下标为0的地方赋初值height[0]不需要进行比较，然后从下标1到n-1进行遍历。具体的可以参考下图

image-20240411110248283

1
2
3
4
5
6
7
8
9
10
rHeight = [0] * n
lHeight = [0] * n
# 计算每个柱子左侧的最高高度
lHeight[0] = height[0]
for i in range(1, n - 1):
    lHeight[i] = max(lHeight[i - 1], height[i])
# print(lHeight)
rHeight[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):
    rHeight[i] = max(rHeight[i + 1], height[i])

找到左边和右边的最高值，计算一列可以装的水有多少

记录每个柱子左边的最高高度和右边的最高高度，然后高度就是min(左边最高高度，右边最高高度)-height[i]，宽度就是1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def trap(self, height: List[int]) -> int:
        # 双指针
        n = len(height)
        if n<=2:
            return 0
        res = 0
        lheight = [0]*n
        rheight = [0]*n
        lheight[0] = height[0]   # 进行初始化
        for i in range(1,n-1):
            lheight[i] = max(lheight[i-1],height[i])
        rheight[n-1] = height[n-1] # 进行初始化
        for i in range(n-2,-1,-1):
            rheight[i] = max(rheight[i+1],height[i])
        # print(lheight,rheight)
        for i in range(1,n-1):
            res += min(lheight[i],rheight[i])-height[i]
        return res

image-20240120203014116

  • 单调栈【逐行累加】

单调栈的核心思路是逐行进行累加

单调栈的思路就是如果栈为空，则先第一个柱子入栈，紧接着如果第二个柱子的高度低于栈中柱子的高度，则继续入栈。也就是说此时栈中的元素从栈顶到栈底是从小到大的顺序。只有从小到大的顺序才能够再下一次遇到一个比栈顶元素高的柱子的时候形成一个凹槽，然后计算能够装的雨水的体积是多少。

如果遇到相同高度的柱子，这时我们需要保存的是最新的下标，这里需要将原来的栈顶元素pop弹出，然后将当前的下标i放到栈顶中。

如果出现一种情况是当前遍历的高度高于栈顶元素的高度，那么弹出栈顶元素，此时如果栈不为空，则开始计算雨水。此时的栈顶的元素的高度就是凹槽的高度，当前遍历的就是凹槽右边的高度，然后栈顶的下一个元素就是左侧的较高的柱子。right-left-1就是宽度，乘以min(left,right)-height[i]就是最终的面积。

这里详细解释一下面积计算的方法：长×高

长 = 当前遍历的下标位置 - 左侧最高高度下标位置 - 1

高 = min(左侧最高高度，右侧最高高度) - 当前柱子高度，具体体现为当前遍历元素为右侧最高高度，栈顶的元素为凹槽处的高度，栈顶的下一个元素为左侧最高高度。

例如下面这张图中，当我遍历到位置5的时候，其计算其长度应该5-1-1=3，然后高度为min(3,2)-1 = 1，所以面积就是3*1=3。可以看出来这一行的面积确实就是3，符合我们的计算公式。

image-20240411113049855

具体的分为下面三种情况：

  • 当前遍历的柱子的高度低于栈顶元素的高度，则继续入栈；
  • 当前遍历的柱子的高度等于栈顶元素的高度，则将栈顶元素弹出，更新最新柱子高度，将新的柱子下标入栈；
  • 当前遍历的柱子的高度大于栈顶元素的高度，此时形成凹槽了，就计算雨水的面积了。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def trap(self, height: List[int]) -> int:
        st = []
        res = 0
        for index, h in enumerate(height):
            while st and height[st[-1]] < h:
                j = st.pop()
                if st:
                    res += (index - st[-1] - 1) * (min(h, height[st[-1]]) - height[j])
            if st and height[st[-1]] == h:
                st.pop()
            st.append(index)
        return res

image-20240123131038428

84、柱状图中最大的矩形

image-20240120215320063

image-20240120215333944

image-20240120215345777

  • 暴力解法

在暴力解法中，从每个下标i位置出发，找到左右两侧比其高的位置，但是一旦出现比其低的位置直接break，记录下左右下边left和right，然后用right-left-1作为底面宽度，height[i]作为高度，得到最终的面积。将这个面积与sum_进行比较，取两者中的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # 暴力解法
        sum_ = 0
        for i in range(len(heights)):
            left, right = i, i
            while left >= 0:
                if heights[left] < heights[i]:
                    break
                left -= 1
            while right < len(heights):
                if heights[right] < heights[i]:
                    break
                right += 1
            sum_ = max(sum_, (right - left - 1) * heights[i])
        return sum_

image-20240121124949045

  • 双指针法

记录每个柱子左边的第一个小于该柱子的下标，而不是记录左边第一个小于该柱子的高度

双指针的难点就在于如何去寻找当前位置i的左右两侧第一个比其低的柱子的下标

此部分的代码如下：

这里在寻找的时候需要进行初始化，不然的话while循环可能死循环。

注意这里如果minLeftIndex数组中元素值为-1或者minRightIndex数组中元素值为len(heights)表示该柱子左边或者右边没有比其更矮的柱子，此时就以这个柱子的高度乘以宽度即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
minLeftIndex[0] = -1
for i in range(1,n):
    t = i-1
    while t>=0 and heights[t]>=heights[i]:
        t = minLeftIndex[t]  # 左移
    minLeftIndex[i] = t
# print(minLeftIndex)
minRightIndex[n-1] = n
for i in range(n-2,-1,-1):
    t = i+1
    while t<=n-1 and heights[t]>=heights[i]:
        t = minRightIndex[t]
    minRightIndex[i] = t

完整代码如下：

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
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # 双指针法
        n = len(heights)
        minLeftIndex = [0]*n
        minRightIndex = [0]*n
        # 寻找左边的小于他的下标
        minLeftIndex[0] = -1
        for i in range(1,n):
            t = i-1
            while t>=0 and heights[t]>=heights[i]:
                t = minLeftIndex[t]  # 左移
            minLeftIndex[i] = t
        # print(minLeftIndex)
        minRightIndex[n-1] = n
        for i in range(n-2,-1,-1):
            t = i+1
            while t<=n-1 and heights[t]>=heights[i]:
                t = minRightIndex[t]
            minRightIndex[i] = t
        # print(minRightIndex)
        res = 0
        for i in range(n):
            res = max(res,(minRightIndex[i]-minLeftIndex[i]-1)*heights[i])
        return res

image-20240122135645235

  • 单调栈法

在接雨水一题中，我们想要实现的效果是寻找到一个凹槽，即找到一个柱子左右两侧高于该柱子的柱子，然后逐行求面积。而本题所需要实现的效果是寻找一个柱子左右两侧低于该柱子的柱子。

单调栈中的顺序（从栈顶到栈底）应该是从大到小的。这样就方便找到每个节点的左边或者右边低于其高度的柱子。当遍历到下一个柱子的高度小于栈顶元素的时候，就可以进行弹出了。在弹出的时候计算高度即可得到最终的答案。

本质上这道题跟接雨水差不多，都可以分成如下三种情况：

  • 情况1：当前遍历的元素height[i]大于栈顶元素height[st[-1]]，此时需要入栈
  • 情况2：当前遍历的元素height[i]等于栈顶元素height[st[-1]]，此时需要将栈顶元素弹出，然后更新最新的柱子高度对应的下标
  • 情况3：当前遍历的元素height[i]小于栈顶元素height[st[-1]]，此时可以进行面积的计算了

计算面积的时候，高度是中间的高度

本题还有一个需要注意的细节，就是需要再heights数组的开头和结尾加上一个0元素，这是因为：

如果数组原本就是一个升序的，如[1,2,3,4,5]，进入栈中变成[5,4,3,2,1]，就不会走情况3，进行面积的计算，所以需要在最后加上0，强制让其进行结果的计算

如果数组原本就是一个降序的，如[5,4,3,2,1]，进入栈中，就会导致无法计算面积，因为目前栈中还是空的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # 单调栈
        heights.insert(0,0)
        heights.append(0)
        stack = [0]
        res = 0
        for i in range(1,len(heights)):
            if heights[i]>heights[stack[-1]]:
                stack.append(i)
            elif heights[i]==heights[stack[-1]]:
                stack.pop()
                stack.append(i)
            else:
                while stack and heights[i] < heights[stack[-1]]:
                    mid = stack.pop()
                    if stack:
                        left_index = stack[-1]
                        right_index = i
                        width = right_index - left_index - 1
                        height = heights[mid]
                        res = max(res,width*height)
                stack.append(i)
        return res

image-20240122165125227

优化版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.append(0)
        heights.insert(0,0)
        st = []
        res = 0
        for index,h in enumerate(heights):
            while st and h<heights[st[-1]]:
                # 开始进行计算面积
                mid = st.pop()
                if st:
                    left = st[-1]
                    right = index
                    res = max(res,heights[mid]*(right-left-1))
            if st and heights[st[-1]]==h:
                st.pop()
            st.append(index)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.insert(0, 0)
        heights.append(0)
        # print(heights)
        st = []
        res = 0
        for index in range(len(heights)):
            while st and heights[st[-1]] > heights[index]:
                # 计算面积
                j = st.pop()
                if st:
                    res = max(res, (index - st[-1] - 1) * heights[j])
            if st and heights[st[-1]] == heights[index]:
                st.pop()
            st.append(index)
        return res

image-20240411145825943

1944、队列中可以看到的人数

image-20240105170740011

image-20240105170750651

image-20240105170804493

题目解析：本题需要计算一个人能看到其右边的人的人数，如果两个人中间还有其他人，并且前一个人的高度高于后一个人的高度，则后面这个人是无法被看见的。

单调栈的本质：及时去掉没有用的数据。

本题单调栈中存放的是人的高度，并且单调栈中的元素从栈顶到栈底是一个递增的顺序。

本题不是采取的从前往后进行遍历的方式，这样的遍历方式无法避免掉被阻挡掉的矮个子；因此需要从后往前进行遍历，如果当前人的高度比栈中的人的高度高，则栈中元素弹出，并且当前人可以看到的人数加1，同时如果栈不为空的情况，当前的人还可以看到一个人需要加1，然后将当前人的高度入栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        n = len(heights)
        ans = [0]*n
        st = []

        for i in range(n-1,-1,-1):
            while st and st[-1]<heights[i]:
                st.pop()
                ans[i]+=1
            if st:
                ans[i]+=1
            st.append(heights[i])
        
        return ans

image-20240105170722984