单调栈

739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

1
2
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

1
2
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

1
2
输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

  • 1 <= temperatures.length <= 105
  • 30 <= temperatures[i] <= 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:

        # 维护单调递减战

        stack = []
        res = [0] * len(temperatures)

        for idx, tem in enumerate(temperatures):
            while len(stack) > 0 and tem > temperatures[stack[-1]]:
                lowidx = stack.pop()
                res[lowidx] = idx - lowidx
            stack.append(idx)

        return res

496. 下一个更大元素 I

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组ans作为答案，满足ans[i]是如上所述的 下一个更大元素 。

示例 1：

1
2
3
4
5
6
输入：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 。

示例 2：

1
2
3
4
5
输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。

提示：

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 104
  • nums1和nums2中所有整数 互不相同
  • nums1 中的所有整数同样出现在 nums2 中

**进阶：**你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ans = [-1 for _ in range(len(nums1))]
        # 构建字典
        dict4n1 = {}
        for idx in range(len(nums1)):
            dict4n1[nums1[idx]] = idx

        # 维护的单调栈存的是元素值
        stack = []
        for idx in range(len(nums2)):
            while stack and nums2[idx] > stack[-1]:
                low_value = stack.pop()
                # 字典找位置
                ans_idx = dict4n1.get(low_value)
                if ans_idx is not None:
                    ans[ans_idx] = nums2[idx]

            stack.append(nums2[idx])

        return ans

503. 下一个更大元素 II

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

示例 1:

1
2
3
4
5
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

示例 2:

1
2
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

提示:

  • 1 <= nums.length <= 104
  • -109 <= nums[i] <= 109
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        double_nums = nums + nums
        stack = []
        ans = [-1 for _ in range(len(nums))]

        # stack 维护下标
        for idx in range(len(double_nums)):
            while stack and double_nums[idx] > double_nums[stack[-1]]:
                low_idx = stack.pop()
                if low_idx < len(nums):
                    ans[low_idx] = double_nums[idx]

            stack.append(idx)

        return ans

42. 接雨水

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

示例 1：

1
2
3
输入：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：

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

提示：

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105
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 trap(self, height: List[int]) -> int:
        # 维护两个数组，左边最大是多少，右边最大是多少
        maxL = []
        temp = 0
        for i in range(len(height)):
            maxL.append(temp)
            if height[i] > temp:
                temp = height[i]

        maxR = []
        temp = 0
        for i in range(len(height)-1, -1, -1):
            maxR.append(temp)
            if height[i] > temp:
                temp = height[i]

        maxR=maxR[::-1]
        
        # 取两遍最小的和自己的差值
        rain = 0
        for i in range(len(height)):
            rain += max(min(maxL[i]-height[i], maxR[i]-height[i]), 0)
        return rain

84. 柱状图中最大的矩形

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

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

示例 1:

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

示例 2：

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

提示：

  • 1 <= heights.length <=105
  • 0 <= heights[i] <= 104
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:
        # 维护一个单调递增的站
        stack = []
        ans = 0
        heights = [0] + heights + [0]
        # 边界：
        for i, height in enumerate(heights):
            # print(stack)
            while len(stack) > 0 and height < heights[stack[-1]]:
                highIdx = stack.pop()
                # print(f"{highIdx = },try:{(highIdx - stack[-1])*heights[highIdx]}")
                # right = i - 1, left = stack[-1] 
                ans = max(ans, (i-1-stack[-1])*heights[highIdx])
            stack.append(i)
            # ans = max(ans, height)
        return ans