leetcode分类刷题：栈（Stack）（三、下一个更大的数）

1、本次博客总结的“栈（Stack）（三、下一个更大的数）”类型具体是指寻找任一个元素的右边/左边第一个比自己大/小的元素的位置，这与栈的先入后出思想一致
2、这种题目用栈处理的算法模板往往叫做单调栈，是因为这种题目代码写完，刚好操作的栈内元素满足单调递增或者递减的规律，本质上还是题型题意符合栈的先入后出思想，所以才使用栈来处理，先入为主地按照单调栈来套模板不是很合适：是先有题型需要用栈处理刚好有个单调栈，不是先有单调栈要去套用解题

739. 每日温度

下一个更大的数的基础题目：正向遍历即可，分三种情况：栈为空遍历索引入栈；小于栈顶元素遍历索引入栈；大于栈顶元素则满足题意持续出栈——感觉单调栈是因为这种处理形成的，并不是先确定单调栈模板的

from typing import List
'''
739. 每日温度
给定一个整数数组temperatures，表示每天的温度，返回一个数组answer，其中answer[i]是指对于第 i 天，下一个更高温度出现在几天后。
如果气温在这之后都不会升高，请在该位置用0 来代替
示例 1:
    输入: temperatures = [73,74,75,71,69,72,76,73]
    输出: [1,1,4,2,1,1,0,0]
题眼：寻找任一个元素的右边/左边第一个比自己大/小的元素的位置，与栈的先入后出思想一致
思路：正向遍历，分三种情况：栈为空遍历索引入栈；小于栈顶元素遍历索引入栈；大于栈顶元素则满足题意持续出栈——感觉单调栈是因为这种处理形成的，并不是先确定
单调栈模板的。
'''


class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        result = [0] * len(temperatures)
        stk = []
        for i in range(len(temperatures)):
            if len(stk) == 0:  # 栈为空，则让索引入栈
                stk.append(i)
            else:
                if temperatures[i] <= temperatures[stk[-1]]:  # 入栈：当前元素小于等于栈顶元素
                    stk.append(i)
                else:
                    while len(stk) > 0 and temperatures[i] > temperatures[stk[-1]]:  # 出栈：当前元素大于栈顶元素
                        result[stk[-1]] = i - stk[-1]
                        stk.pop()
                    stk.append(i)
        return result


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')
            temperatures = [int(n) for n in in_line[1].strip()[1: -1].split(',')]
            print(obj.dailyTemperatures(temperatures))
        except EOFError:
            break
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
35
36
37
38
39
40
41

496. 下一个更大元素 I

下一个更大的数的基础题目：这里序列中元素不重复了，那么元素和索引都是唯一标识（二分查找的那种最简单题型也是元素不重复），也更加简单了

from typing import List
'''
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:
    输入：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 。
题眼：寻找任一个元素的右边/左边第一个比自己大/小的元素的位置，与栈的先入后出思想一致
思路：1、遍历nums2建立下一个更大元素的hashTable（元素不重复才能在这里用哈希表）——不重复也意味着元素和索引都是唯一标识
     2、遍历nums1寻找结果
'''


class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 第一步，建立nums2中下一个更大元素的哈希表
        hashTable = {}
        stk = []  # 定义栈之后，思考下入栈的是索引还是元素，这里元素不重复意味着索引与元素都是唯一标识
        for i in range(len(nums2)):
            if len(stk) == 0:
                stk.append(i)
            else:
                if nums2[i] < nums2[stk[-1]]:  # 无重复，所以不用加等于
                    stk.append(i)
                else:
                    while len(stk) > 0 and nums2[i] > nums2[stk[-1]]:
                        hashTable[nums2[stk[-1]]] = nums2[i]
                        stk.pop()
                    stk.append(i)
        # 第二步，建立结果数组
        result = [-1] * len(nums1)
        for i in range(len(nums1)):
            if nums1[i] in hashTable:
                result[i] = hashTable[nums1[i]]
        return result


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')
            in_line1 = in_line[1].split('[')[1].split(']')[0]
            in_line2 = in_line[2].split('[')[1].split(']')[0]
            nums1 = [int(n) for n in in_line1.split(',')]
            nums2 = [int(n) for n in in_line2.split(',')]
            print(obj.nextGreaterElement(nums1, nums2))
        except EOFError:
            break
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

503. 下一个更大元素 II

下一个更大的数的基础题目：这里要求对循环数组操作，有了对leetcode分类刷题：字符串匹配KMP算法中686. 重复叠加字符串匹配循环匹配的经验，这道题目一点也不难：循环两次遍历数组，且不用对最后一个元素访问第二次

from typing import List
'''
503. 下一个更大元素 II
给定一个循环数组nums（nums[nums.length - 1]的下一个元素是nums[0]），返回nums中每个元素的 下一个更大元素 。
数字 x的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
示例 1:
    输入: nums = [1,2,1]
    输出: [2,-1,2]
    解释: 第一个 1 的下一个更大的数是 2；
    数字 2 找不到下一个更大的数；
    第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
题眼：寻找任一个元素的右边/左边第一个比自己大/小的元素的位置，与栈的先入后出思想一致
思路：循环两次遍历数组，且不用对最后一个元素访问第二次
'''


class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        # 循环两次遍历数组，且不用对最后一个元素访问第二次
        stk = []
        result = [-1] * len(nums)
        for i in range(len(nums) * 2 - 1):
            if len(stk) == 0:
                stk.append(i % len(nums))
            else:
                if nums[i % len(nums)] <= nums[stk[-1]]:
                    stk.append(i % len(nums))
                else:
                    while len(stk) > 0 and nums[i % len(nums)] > nums[stk[-1]]:
                        result[stk[-1]] = nums[i % len(nums)]
                        stk.pop()
                    stk.append(i % len(nums))
        return result


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')
            in_line1 = in_line[1].split('[')[1].split(']')[0]
            nums = [int(n) for n in in_line1.split(',')]
            print(obj.nextGreaterElements(nums))
        except EOFError:
            break
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
35
36
37
38
39
40
41
42
43
44
45

42. 接雨水

1、下一个更大的数的变体题目，即左右两边下一个最大的数：这道题目最关键的地方在于理解题目，每个位置接雨水的量取决于左右两边的最大值，因此按照该思路定义两个数组，分别保存左右两边的最大值，然后再次遍历序列依次累计雨水量即可
2、这道题也可以按照单调栈的解法思路：按照“大小大”规律求夹着的面积，与栈的先入后出思想一致：小于栈顶元素入栈；等于栈顶元素则替换栈顶元素；大于栈顶元素则判断“大小大”计算面积，按照行为单位求雨水量
3、这道题还可以用双指针的解法思路：左右指针从两侧同时遍历，并分别维护左右两侧的最大值标记，哪个指针对应的元素小就更新哪个，等价于哪个指针可以根据两个最大值标记计算接水量，
就移动哪个指针；这个思路巧妙但更难了，不是太常规

from typing import List
'''
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 个单位的雨水（蓝色部分表示雨水）。
题眼：
思路1、模拟：每个位置接雨水的量取决于左右两边的最大值，因此，定义两个数组，分别保存左右两边的最大值（包括自己，闭区间考虑）；这种思路是按照列为单位求
雨水量的，简单直观，建议掌握！
思路2、单调栈：按照“大小大”规律求夹着的面积，与栈的先入后出思想一致：小于栈顶元素入栈；等于栈顶元素则替换栈顶元素；大于栈顶元素则判断“大小大”计算面积；
这种思路按照行为单位求雨水量的，这种解释不是太好理解，还不如按照括号配对的思路理解，按照这种思路有点难
思路3、双指针：左右指针从两侧同时遍历，并分别维护左右两侧的最大值标记，哪个指针对应的元素小就更新哪个，等价于哪个指针可以根据两个最大值标记计算接水量，
就移动哪个指针；这个思路巧妙但更难了，不是太常规，理解起来有点吃力
'''


class Solution:
    def trap(self, height: List[int]) -> int:
        # # 思路1、模拟：每个位置接雨水的量取决于左右两边的最大值，因此，定义两个数组，分别保存左右两边的最大值（包括自己，闭区间考虑）
        # lmax = [0] * len(height)
        # maxNum = 0
        # for i in range(len(height)):
        #     maxNum = max(maxNum, height[i])
        #     lmax[i] = maxNum
        # rmax = [0] * len(height)
        # maxNum = 0
        # for i in range(len(height) - 1, -1, -1):
        #     maxNum = max(maxNum, height[i])
        #     rmax[i] = maxNum
        # result = 0
        # for i in range(len(height)):
        #     result += min(lmax[i], rmax[i]) - height[i]
        # return result

        # # 思路2、单调栈：按照“大小大”规律求夹着的面积，与栈的先入后出思想一致：小于栈顶元素入栈；等于栈顶元素则替换栈顶元素；
        # # 大于栈顶元素则判断“大小大”计算面积
        # stk = []
        # result = 0
        # for i in range(len(height)):
        #     if len(stk) == 0:
        #         stk.append(i)
        #     else:
        #         if height[i] < height[stk[-1]]:
        #             stk.append(i)
        #         elif height[i] == height[stk[-1]]:  # 这一步可以注释掉，合并到上一步入栈
        #             stk.pop()
        #             stk.append(i)
        #         elif height[i] > height[stk[-1]]:
        #             while len(stk) > 0 and height[i] > height[stk[-1]]:
        #                 right = height[i]
        #                 mid = height[stk.pop()]
        #                 if len(stk) > 0:
        #                     left = height[stk[-1]]
        #                     result += (min(left, right) - mid) * (i - stk[-1] - 1)
        #             stk.append(i)
        # return result

        # 思路3、双指针：左右指针从两侧同时遍历，并分别维护左右两侧的最大值标记，哪个指针对应的元素小就更新哪个，等价于哪个指针可以根据两个最大值标
        # 记计算接水量，就移动哪个指针
        left, right = 0, len(height) - 1
        lMax, rMax = height[left], height[right]  # lMax标记了left位置的左侧最大值（包括left本身）；rMax标记了right位置的右侧最大值
        # （包括right本身）
        result = 0
        while left < right:  # left==right时，表示定位到了数组中的最大值处了，这里不用计算，肯定不能接水
            if height[left] <= height[right]:  # 情况1：height[left]刚好为lMax，必有lMax<=rMax；情况2：height[left]之前的某个数
                # 为lMax，那么当时left能更新的条件必然是lMax<=rMax；那么在left位置，必然有lMax<=left位置自己的右侧最大值（本来就比rMax大）
                # 所以，left指针可以记计算接水量
                result += lMax - height[left]  # 因为lMax包含了left位置，所以不用担心该计算小于0
                left += 1
                lMax = max(lMax, height[left])
            elif height[left] > height[right]:  # 情况1：height[right]刚好为rMax，必有lMax>rMax；情况2：height[right]之前的某个数
                # 为lMax，那么当时right能更新的条件必然是lMax>rMax；那么在right位置，必然有right位置自己的左侧最大值（本来就比lMax大）>rMax
                # 所以，right指针可以记计算接水量
                result += rMax - height[right]  # 因为rMax包含了right位置，所以不用担心该计算小于0
                right -= 1
                rMax = max(rMax, height[right])
        return result


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')
            height = [int(n) for n in in_line[1].strip()[1: -1].split(',')]
            print(obj.trap(height))
        except EOFError:
            break
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

84. 柱状图中最大的矩形

1、下一个更大的数的变体题目，即左右两边下一个更小的数：这道题目最关键的地方也是在于理解题目，每个位置的最大矩形面积取决于左右两侧第一个小于当前值的索引，分别用两个单调栈求解每个位置的左右两侧第一个小于当前值的索引，然后再次遍历原序列求每个位置的最大矩形面积；这种思路简单直观
2、这道题也可以按照单调栈的解法思路：寻找“小大小”的组合进行出栈：大于栈顶元素入栈；等于栈顶元素时进行替换（最大面积与栈顶元素相同）；小于栈顶元素出栈求最大矩形面积；最后把栈内剩余元素也处理完

from typing import List
'''
84. 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
    输入：heights = [2,1,5,6,2,3]
    输出：10
    解释：最大的矩形为图中红色区域，面积为 10
题眼：读懂题很重要，每个位置的最大矩形面积取决于左右两侧第一个小于当前值的索引
思路1、模拟：分别用两个单调栈求解每个位置的左右两侧第一个小于当前值的索引，然后再次遍历原序列求每个位置的最大矩形面积；这种思路简单直观！
思路2、单调栈：寻找“小大小”的组合进行出栈：大于栈顶元素入栈；等于栈顶元素时进行替换（最大面积与栈顶元素相同）；小于栈顶元素出栈求最大矩形面积；最后把栈内
剩余元素也处理完
'''


class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # # 思路1、模拟：分别用两个单调栈求解每个位置的左右两侧第一个小于当前值的索引，然后再次遍历原序列求每个位置的最大矩形面积
        # rmin = [len(heights)] * len(heights)
        # stk = []
        # for i in range(len(heights)):
        #     if len(stk) == 0:
        #         stk.append(i)
        #     else:
        #         if heights[i] >= heights[stk[-1]]:
        #             stk.append(i)
        #         else:
        #             while len(stk) > 0 and heights[i] < heights[stk[-1]]:
        #                 rmin[stk[-1]] = i
        #                 stk.pop()
        #             stk.append(i)
        #
        # lmin = [-1] * len(heights)
        # stk = []
        # for i in range(len(heights) - 1, -1, -1):
        #     if len(stk) == 0:
        #         stk.append(i)
        #     else:
        #         if heights[i] >= heights[stk[-1]]:
        #             stk.append(i)
        #         else:
        #             while len(stk) > 0 and heights[i] < heights[stk[-1]]:
        #                 lmin[stk[-1]] = i
        #                 stk.pop()
        #             stk.append(i)
        # result = 0
        # for i in range(len(heights)):
        #     result = max(result, heights[i] * (rmin[i] - lmin[i] - 1))
        # return result

        # 思路2、单调栈：寻找“小大小”的组合进行出栈：大于栈顶元素入栈；等于栈顶元素时进行替换（最大面积与栈顶元素相同）；小于栈顶元素出栈求最大矩形
        # 面积；最后把栈内剩余元素也处理完
        stk = []
        result = 0
        for i in range(len(heights)):
            if len(stk) == 0:
                stk.append(i)
            else:
                if heights[i] > heights[stk[-1]]:
                    stk.append(i)
                elif heights[i] == heights[stk[-1]]:  # 这一步可以注释掉，合并到上一步入栈
                    stk.pop()
                    stk.append(i)
                elif heights[i] < heights[stk[-1]]:
                    while len(stk) > 0 and heights[i] < heights[stk[-1]]:
                        mid = stk.pop()
                        left = -1 if len(stk) == 0 else stk[-1]
                        result = max(result, heights[mid] * (i - left - 1))
                    stk.append(i)
        # 最后把栈内剩余元素也处理完
        while len(stk) > 0:
            mid = stk.pop()
            left = -1 if len(stk) == 0 else stk[-1]
            result = max(result, heights[mid] * (len(heights) - left - 1))
        return result


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')
            in_line1 = in_line[1].split('[')[1].split(']')[0]
            nums = [int(n) for n in in_line1.split(',')]
            print(obj.largestRectangleArea(nums))
        except EOFError:
            break
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

85. 最大矩形

这道题确实太难了，不看题解根本想不到：需要先以每行为基准，统计连续1的个数，把每行都转换为“84. 柱状图中最大的矩形”的求解模板，参考大佬的解法

from typing import List
'''
85. 最大矩形
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例 1:
    输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
    输出：6
思路：这道题确实太难了，不看题解根本想不到：需要先以每行为基准，统计连续1的个数，转换为“84. 柱状图中最大的矩形”的求解模板
'''


class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if len(matrix) == 0:
            return 0
        # 第一步，先以每行为基准，统计连续1的个数，转换为柱状图的形式
        m, n = len(matrix), len(matrix[0])
        matrix2 = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if i == 0:
                    if matrix[i][j] == '1':
                        matrix2[i][j] = 1
                else:
                    if matrix[i][j] == '1':
                        matrix2[i][j] = matrix2[i-1][j] + 1
        # 第二步，按照“84. 柱状图中最大的矩形”的求解模板对每一行进行求解
        result = 0
        for i in range(m):
            # 1、求右侧下一个更小的索引
            rmin = [n] * n
            stk = []
            for j in range(n):
                if len(stk) == 0:
                    stk.append(j)
                else:
                    if matrix2[i][j] >= matrix2[i][stk[-1]]:
                        stk.append(j)
                    else:
                        while len(stk) > 0 and matrix2[i][j] < matrix2[i][stk[-1]]:
                            rmin[stk[-1]] = j
                            stk.pop()
                        stk.append(j)
            # 2、求左侧下一个更小的索引
            lmin = [-1] * n
            stk = []
            for j in range(n - 1, -1, -1):
                if len(stk) == 0:
                    stk.append(j)
                else:
                    if matrix2[i][j] >= matrix2[i][stk[-1]]:
                        stk.append(j)
                    else:
                        while len(stk) > 0 and matrix2[i][j] < matrix2[i][stk[-1]]:
                            lmin[stk[-1]] = j
                            stk.pop()
                        stk.append(j)
            # 3、求每个遍历元素的最大矩形面积
            for j in range(n):
                result = max(result, matrix2[i][j] * (rmin[j] - lmin[j] - 1))

        return result


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')
            matrix = []
            if in_line[1].strip()[1: -1] == "":
                matrix = []
            else:
                for s in in_line[1].strip()[1: -1].split(']')[: -1]:
                    row = []
                    for ch in s.split('[')[1].split(','):
                        row.append(ch[1: -1])
                    matrix.append(row)
            print(obj.maximalRectangle(matrix))
        except EOFError:
            break
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81