1

pair.sort(key=lambda x:x[0], reverse=True)

 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

class Solution:
    def carFleet(self, target, position, speed) -> int:
        """
        计算到达终点的车队数量。多辆车如果能在同一时间到达终点，就算作一个车队。

        参数:
        - target: 终点位置
        - position: 每辆车的初始位置列表
        - speed: 每辆车的速度列表

        返回:
        - 车队数量（最终独立到达终点的车辆组数）
        """
        
        # 将每辆车的位置和到达终点的所需时间配对
        # 公式：(目标位置 - 当前位置)/速度 = 到达时间
        pair = [(p, (target-p)/s) for p, s in zip(position, speed)]
        
        # 按位置从近到远排序（离终点远的车排前面）
        pair.sort()
        
        # 维护一个单调栈（栈顶是最快到达终点的时间）
        stk = []
        
        # 遍历每个车辆数据（从最近的到最远的）
        for _, time in pair:
            # 如果当前车的到达时间 >= 栈顶车队的到达时间，
            # 说明当前车会追上栈顶车队（成为一个车队）
            while stk and time >= stk[-1]:
                stk.pop()  # 合并车队
                
            # 将当前车的到达时间压入栈（代表一个新的潜在车队）
            stk.append(time)
        
        # 栈的大小就是独立车队数量
        return len(stk)

 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

class Solution:
    def carFleet(self, target, position, speed) -> int:
        """
        计算会形成多少个车队。当后车到达时间严格大于前车时，才能形成独立车队。
        采用从近到远遍历，只保留严格递增的到达时间序列。

        参数:
        - target: int, 目标位置
        - position: List[int], 每辆车的初始位置
        - speed: List[int], 每辆车的速度

        返回:
        - int, 车队数量
        """
        # 创建(位置, 到达时间)元组并按位置降序排列（近的车排在前面）
        pair = [(p, (target-p)/s) for p, s in zip(position, speed)]
        
        # 按位置从远到近排序（离终点近的车排前面）
        pair.sort(reverse=True)
        
        stk = []
        for _, time in pair:
            # 只有比栈顶更大的才会入栈
            if not stk or time > stk[-1]:
                stk.append(time)
        
        # 栈中元素个数就是独立车队数量
        return len(stk)

 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

class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        """
        计算数组中的最大宽度坡，坡定义为i <= j且nums[i] <= nums[j]
      
        参数:
        - nums: List[int]，输入数组
      
        返回:
        - int，最大宽度坡的长度
        """
        stk = []
        # 遍历数组，构造单调递减栈（存储索引）
        # 栈中元素满足：nums[stk[i]] > nums[stk[i+1]] 
        for i, x in enumerate(nums):
            # 当栈为空或当前元素小于栈顶元素时才入栈
            if not stk or x < nums[stk[-1]]:
                stk.append(i)
      
        res = 0
        # 从数组末尾向前遍历
        for i in range(len(nums)-1, -1, -1):
            # 当栈不为空且当前元素大于等于栈顶元素时
            while stk and nums[i] >= nums[stk[-1]]:
                # 计算当前坡的宽度，并更新最大值
                res = max(res, i - stk.pop())
      
        return res

1
2
3
4
5
6
7

stk = []
# 遍历数组，构造单调递减栈（存储索引）
# 栈中元素满足：nums[stk[i]] > nums[stk[i+1]] 
for i, x in enumerate(nums):
	# 当栈为空或当前元素小于栈顶元素时才入栈
	if not stk or x < nums[stk[-1]]:
		stk.append(i)

1
2
3
4
5
6
7

res = 0
# 从数组末尾向前遍历
for i in range(len(nums)-1, -1, -1):
	# 当栈不为空且当前元素大于等于栈顶元素时
	while stk and nums[i] >= nums[stk[-1]]:
		# 计算当前坡的宽度，并更新最大值
		res = max(res, i - stk.pop())

 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

class Solution:
    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
        """
        计算在满足特定条件下，山高度数组的最大和。
        条件：每个位置的高度必须<=maxHeights中的对应值，且整体形成山形
        （非严格递增后非严格递减）

        参数:
            maxHeights: 输入的限制高度数组

        返回:
            满足条件的山形数组的最大和

        方法:
        1. 使用单调栈分别计算前后缀信息
        2. 前缀求左侧递增部分（非严格）
        3. 后缀求右侧递减部分（非严格）
        4. 计算每个位置作为峰值时的总最大值
        """
        n = len(maxHeights)
      
        # 计算后缀和数组：suf[i]表示从位置i开始的递减部分最大和
        suf = [0] * (n + 1)  # 额外+1位置便于处理边界情况
        stk = [n]  # 哨兵结点（虚拟的n位置）
        cur = 0     # 当前和初始化为0
        for i in range(n - 1, -1, -1):  # 从右向左遍历
            x = maxHeights[i]
            # 维护单调递增栈（保证能处理递减部分）
            while len(stk) > 1 and x <= maxHeights[stk[-1]]:
                j = stk.pop()
                cur -= (stk[-1] - j) * maxHeights[j]  # 移除弹出元素的影响
            # 添加当前元素的影响
            cur += (stk[-1] - i) * x  # 计算并累积影响范围
            suf[i] = cur  # 存储当前后缀和
            stk.append(i)  # 当前索引入栈

        # 初始化结果和前缀和计算变量
        res = 0
        pre = 0
        stk = [-1]  # 重置栈（左侧哨兵结点）

        # 计算前缀和并合并结果
        for i in range(n):  # 从左向右遍历
            x = maxHeights[i]
            # 维护单调递增栈（保证能处理递增部分）
            while len(stk) > 1 and x <= maxHeights[stk[-1]]:
                j = stk.pop()
                pre -= (j - stk[-1]) * maxHeights[j]  # 移除弹出元素的影响
            # 添加当前元素的影响
            pre += (i - stk[-1]) * x  # 计算并累积影响范围
            # 当前结果=前i个递增部分+i+1开始的递减部分
            res = max(res, pre + suf[i + 1])
            stk.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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        """
        计算直方图中可以构成的最大矩形面积

        参数:
        - heights: 表示直方图每个柱子高度的列表

        返回:
        - int: 最大矩形面积

        算法思路:
        懒计算，遇到不合群的再一次性计算前面的，因此需要前后哨兵
        使用单调栈算法，维护一个高度单调不减的柱子索引栈
        当遇到比栈顶低的柱子时，懒计算以栈顶柱子为高的矩形面积
        """
        
        # 首尾添加高度为0的哨兵节点:
        # 开头的0保证第一个柱子能被正确计算
        # 末尾的0保证剩余栈中的柱子能被弹出计算
        heights = [0] + heights + [0]  
        stk = []  # 存储柱子索引的单调栈（保持对应高度单调不减）
        res = 0   # 最大面积结果
        
        for i, h in enumerate(heights):
            # 遇到比栈顶低的柱子时，处理所有可以被弹出的柱子
            while stk and h < heights[stk[-1]]:
                # 高度是栈顶索引所对应的高度
                hh = heights[stk.pop()]
                # 矩形实际的左侧，是栈顶下标 + 1
                # 此时的栈顶是最后一个不纳入计算面积的坐标
                ll = stk[-1] + 1
                # 矩形实际的右侧，是当前坐标 - 1
                # 因为走到了当前坐标发现不合适，当前坐标是第一个不合适的
                rr = i - 1
                res = max(res, hh * (rr - ll + 1))
            
            # 将当前柱子索引压入栈
            stk.append(i)
            
        return res

1

heights = [0] + heights + [0]

 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

class Solution:
    def trap(self, height: List[int]) -> int:
        """
        计算柱子高度数组能接住的雨水量。

        参数:
        - height: List[int]，表示每个柱子的高度。
        
        返回:
        - int，表示能接住的雨水总量。
        """
        
        n = len(height)
        
        # 初始化左右最大高度数组
        # l[i]表示第i个柱子左边（包括自身）的最大高度
        # r[i]表示第i个柱子右边（包括自身）的最大高度
        l, r = [0] * n, [0] * n
        
        # 设置边界条件
        l[0] = height[0]
        r[n-1] = height[n-1]
        
        # 从左向右遍历，填充左最大高度数组
        for i in range(1, n):
            l[i] = max(l[i-1], height[i]) 
            
        # 从右向左遍历，填充右最大高度数组
        for i in range(n-2, -1, -1):
            r[i] = max(r[i+1], height[i])
            
        res = 0  # 初始化雨水总量
        
        # 计算每个柱子的雨水贡献
        for i in range(n):
            # 每个柱子的雨水高度 = 最小左右边界高度 - 当前柱子高度
            res += min(l[i], r[i]) - height[i]
        
        return res

 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

class Solution:
    def trap(self, height: List[int]) -> int:
        """
        使用单调栈计算柱状图可接雨水量。
        
        参数:
        - height: List[int], 表示每个柱子的高度
        
        返回:
        - int, 能接的雨水总量
        """

        res = 0  # 初始化雨水总量
        stk = []  # 单调栈，存储柱子索引，栈底到栈顶保持递减（按高度）

        for i, h in enumerate(height):  # 遍历每个柱子
            # 维护单调栈性质 - 当前柱子高于栈顶柱子时处理
            while stk and h > height[stk[-1]]:
                bottem = height[stk.pop()]  # 弹栈得到凹陷的底部高度
                
                # 如果栈不为空，说明存在左边界
                if stk:
                    # 计算当前凹槽的宽度
                    dw = i - stk[-1] - 1
                    # 计算当前凹槽的高度
                    dh = min(height[stk[-1]], h) - bottem
                    # 累计雨水量
                    res += dw * dh
            
            # 将当前柱子索引压入栈
            stk.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
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        """
        计算每天需要等待多少天才能等到更温暖的气温
        
        参数:
        - temperatures: List[int], 每日温度列表
        
        返回:
        - List[int], 结果列表，表示每天需要等待的天数
        """
        
        # 初始化结果列表（后面会逆序存储）
        ans = []
        # 使用单调栈存储温度递减的日期索引
        stk = []
        
        # 从后往前遍历温度列表（便于计算等待天数）
        for i in range(len(temperatures)-1, -1, -1):
            # 维护单调栈：弹出所有温度小于等于当前温度的日期
            while stk and temperatures[stk[-1]] <= temperatures[i]:
                stk.pop()
            
            # 如果栈不为空，栈顶元素就是第一个比当前温度高的日期
            if stk:
                ans.append(stk[-1] - i)  # 计算等待天数
            else:
                ans.append(0)  # 没有更高温度的日期
            
            # 将当前日期压入栈中
            stk.append(i)
        
        # 因为我们是从后往前遍历的，结果需要逆序
        ans = ans[::-1]
        return ans

 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

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        """
        计算商品最终价格（能够使用右边第一个小于等于当前价格的折扣）
      
        参数:
        - prices: List[int], 商品原始价格列表
      
        返回:
        - List[int], 应用折扣后的最终价格列表
        """
      
        # 使用栈存储价格（维护单调递增栈）
        stk = []
        # 存储结果（后面会逆序）
        res = []
      
        # 从后往前遍历价格列表
        for i in range(len(prices)-1, -1, -1):
            # 维护单调递增栈：弹出所有比当前价格大的价格
            while stk and stk[-1] > prices[i]:
                stk.pop()
          
            # 计算最终价格：如果有更低价格就减去折扣，否则保持原价
            # 因为是从后往前遍历，stk[-1]就是右边的第一个≤当前价格的值
            res.append(prices[i] - stk[-1] if stk else prices[i])
          
            # 将当前价格压入栈中
            stk.append(prices[i])
      
        # 反转结果列表（因为是从后往前处理的）
        res = res[::-1]
        return res

 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

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        """
        在nums2中找到每个元素右侧第一个比它大的元素，并返回nums1中对应元素的结果
        
        参数:
        - nums1: List[int], 查询目标列表
        - nums2: List[int], 被查询列表
        
        返回:
        - List[int], nums1中每个元素在nums2中对应的next greater元素列表
        """
        
        # 单调栈：维护一个递减栈，用于快速找到每个元素的next greater element
        stk = []
        # 字典存储nums2中每个元素的next greater element
        nxt = {}
        
        # 从后向前遍历nums2以便找到每个元素右边第一个更大的元素
        for i in range(len(nums2)-1, -1, -1):
            # 弹出栈顶比当前元素小的元素，保证栈顶元素总是比当前元素大
            while stk and stk[-1] <= nums2[i]:
                stk.pop()
            
            # 如果栈不为空，栈顶就是当前元素的next greater element
            # 否则记录-1表示没有更大的元素
            nxt[nums2[i]] = stk[-1] if stk else -1
            
            # 将当前元素压入栈中
            stk.append(nums2[i])
        
        # 返回nums1中每个元素对应的next greater element
        return [nxt[num] for num in nums1]

 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

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        """
        在循环数组中找到每个元素右侧第一个比它大的元素
        
        参数:
        - nums: List[int], 循环数组
        
        返回:
        - List[int], 每个元素的下一个更大元素列表，无则返回-1
        """
        
        n = len(nums)
        stk = []  # 单调栈，维护递减序列
        res = [-1] * n  # 初始化结果为-1（表示默认没有更大的元素）
        
        # 逆序遍历两倍长度（模拟循环数组）
        for i in range(2 * n - 1, -1, -1):
            ii = i % n  # 实际索引（0到n-1之间）
            
            # 维护单调栈：弹出所有<=当前元素的栈顶元素
            while stk and stk[-1] <= nums[ii]:
                stk.pop()
            
            # 栈顶元素即为当前元素的下一个更大元素
            # 处理两遍确保循环情况下也能找到正确结果
            # 后出现的元素会覆盖前面的结果
            if stk:
                res[ii] = stk[-1]
            
            # 将当前元素压入栈中
            stk.append(nums[ii])
        
        return res

 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

class StockSpanner:
    def __init__(self):
        """
        初始化股票价格跨度计算器。
        - stk: 单调栈，保存(index, price)元组，栈中price保持递减顺序
        - 初始压入哨兵(-1, ∞)，避免空栈判断
        - idx: 记录当前是第几个价格输入（从0开始计数）
        """
        self.stk = [(-1, float('inf'))]  # (index, price)栈，初始哨兵节点
        self.idx = -1  # 当前价格索引（初始为-1，next()时先自增）

    def next(self, price: int) -> int:
        """
        计算当前价格的跨度值（连续≤当前价格的天数）

        参数:
        - price: int, 当日股票价格

        返回:
        - int: 跨度值（包括当日）
        """
        self.idx += 1  # 更新当前索引
        
        # 维护单调性：弹出所有≤当前价格的条目
        while price >= self.stk[-1][1]:
            self.stk.pop()
        
        # 计算跨度 = 当前索引 - 栈顶元素的索引
        res = self.idx - self.stk[-1][0]
        
        # 将当前价格和索引进栈
        self.stk.append((self.idx, price))
        
        return res

 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

class Solution:
    def reverseNodes(self, head):
        """
        递归反转链表
        
        参数:
        - head: ListNode，链表头节点
        
        返回:
        - ListNode，反转后的链表头节点
        """
        # 如果链表为空或只有一个节点，直接返回
        if not head or not head.next: 
            return head 
        # 递归反转后续链表
        p = self.reverseNodes(head.next)
        # 将当前节点的下一个节点指向当前节点，实现反转
        head.next.next = head 
        # 断开当前节点的原next指针，避免循环
        head.next = None 
        return p
    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
        """
        找出链表中每个节点后面第一个比它大的节点的值
        
        参数:
        - head: ListNode，链表头节点
        
        返回:
        - List[int]，每个节点后面第一个比它大的节点的值列表
        """
        # 先将链表反转以便处理
        head = self.reverseNodes(head)
        res, stk, cur = [], [], head 
        while cur:
            # 弹出栈中所有小于等于当前节点值的元素
            while stk and stk[-1] <= cur.val:
                stk.pop()
            # 如果栈不为空，栈顶元素即为第一个比当前节点大的值
            res.append(stk[-1] if stk else 0)
            # 将当前节点值压栈
            stk.append(cur.val)
            cur = cur.next 
        # 由于是从后往前处理的，需要将结果反转
        return res[::-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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        """
        计算工作日表现良好的最长区间长度（Well Performing Interval, WPI）
        该区间内"劳累天数"（>8小时）严格多于"不劳累天数"（<=8小时）
        
        参数:
        - hours: 每天工作小时数的列表
        
        返回:
        - 最长表现良好区间的天数
        """
        
        n = len(hours)
        # 前缀和数组，s[0] = 0，s[i]表示前i天的净劳累天数
        # 定义：劳累天+1，不劳累天-1
        s = [0] * (n + 1)
        
        # 单调栈，存储前缀和数组的可能左边界索引
        # 初始化为0，因为s[0]是最小的可能左边界
        stk = [0]
        
        # 第一次遍历：计算前缀和并构建单调栈
        for i, x in enumerate(hours, 1):
            # 计算前缀和
            s[i] = s[i - 1] + (1 if x > 8 else -1)
            
            # 维护单调栈（存放可能的最小左边界）
            if s[i] < s[stk[-1]]:
                stk.append(i)
        
        res = 0
        
        # 第二次遍历：从右往左检查可能的右边界
        for i in range(n, 0, -1):
            # 当前右边界i对应的前缀和s[i]是否大于某个左边界的前缀和
            while stk and s[i] > s[stk[-1]]:
                # 计算区间长度并更新结果
                res = max(res, i - stk.pop())
        
        return res

 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

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        """
        检查数组中是否存在满足1-3-2模式的子序列：
        - i < j < k（下标）
        - nums[i] < nums[k] < nums[j]（值）

        参数：
        - nums: 输入的整数数组

        返回：
        - 存在132模式则返回True，否则返回False
        """

        # two 存储当前可能的"2"值（即中间值）
		"""为什么two只需要一个值：
		1. 我们只需要记录在当前one右侧的、最大的满足two < one的two值
		2. 当遇到更大的one时，two会被更新为更大的值（通过弹栈）
		3. 这个过程保证了two是历史最大值中能满足nums[i] < two的最大可能值
		4. 如果有更小的two能满足条件，那一定已经在之前就被检测到了
		5. 因此只维护一个two值不会漏掉任何可能性
		"""
		two = float('-inf')

        # three 作为单调栈，存储可能的"3"候选元素
        three = []

        # 从后往前遍历数组（确定"1"的位置）
        for i in range(len(nums)-1, -1, -1):
            one = nums[i]  # 潜在的"1"值

            # 如果当前"1"值小于已找到的"2"值，说明找到了完整的132模式
            if one < two:
                return True

            # 如果当前元素比栈顶元素大，则：
            # 1. 栈顶元素一定在i右侧（因为逆向遍历）
            # 2. 栈顶元素可以成为新的潜在的"2"
            # 3. 我们把较小的元素弹出栈，因为它们不可能是更好的"3"候选
            while three and three[-1] < one:
                two = three.pop()  # 弹出栈顶作为新的"2"

            # 当前元素压入栈（成为新的"3"候选）
            three.append(one)

        # 遍历完仍未找到132模式
        return False
        

 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

class Solution:
    def numberOfSubarrays(self, nums: List[int]) -> int:
        """
        计算数组中满足特定条件的子数组数量
        条件：子数组的第一个元素是该子数组的最小值 

        参数:
            nums: 输入整数数组

        返回:
            满足条件的子数组总数

        方法:
        使用单调栈维护元素的频率信息
        时间复杂度: O(n)，每个元素最多入栈出栈一次
        """
        
        # 初始化结果为数组长度（每个单独元素本身就是一个满足条件的子数组）
        res = len(nums)
        # 使用栈存储元组：(当前元素值, 该值作为最小值的连续出现次数)
        stk = []

        for num in nums:
            # 维护单调递增栈：
            # 弹出所有比当前元素小的元素（这些元素不可能再作为后续子数组的最小值）
            while stk and num > stk[-1][0]:
                stk.pop()
            
            # 处理与栈顶相同的元素
            if stk and stk[-1][0] == num:
                # 取出栈顶元素
                val, cnt = stk.pop()
                # 增加的子数组数量等于之前该值的连续出现次数
                res += cnt
                # 更新该值的出现次数（+1）后重新入栈
                stk.append((val, cnt + 1))
            else:
                # 新的元素入栈，初始出现次数为1
                stk.append((num, 1))
        
        return res

 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

class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        """
        计算每个人可以看到的其他人的数量
        规则：
        - 一个人只能看到右侧比他矮的人
        - 如果右侧有更高的人，会挡住后面的视线

        参数:
            heights: 人的身高列表

        返回:
            每个人可以看到的人数列表

        方法:
        使用单调栈（单调递减）
        从右向左遍历，栈顶元素总是最近的可能阻挡视线的更高的人
        时间复杂度：O(n)
        """
        n = len(heights)
        res = [0] * n  # 初始化结果列表
        stk = []  # 使用栈来记录可能阻挡视线的人

        # 从右向左遍历
        for i in range(n - 1, -1, -1):
            # 移除栈中所有比当前人矮的人（这些人都可以被看到）
            while stk and stk[-1] < heights[i]:
                res[i] += 1  # 可以看到这个矮的人
                stk.pop()  # 移除该人（后面会被当前人阻挡）

            # 如果栈不为空，说明遇到了一个更高的或相等的人
            # 可以看到这个人（最后一个阻挡视线的人）
            if stk:
                res[i] += 1

            # 将当前人放入栈中（会成为后面人的潜在阻挡）
            stk.append(heights[i])

        return res

 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

```python
class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        """
        找出每个元素的第二个更大的元素
        对于nums[i]，找到nums[j]满足：
        1. j > i
        2. nums[j] > nums[i]
        3. 存在k>i使得nums[k]>nums[i]且j是第二个满足该条件的元素

        参数:
        - nums: 输入的数字列表

        返回:
        - res: 每个元素的第二个更大的元素列表，没有则返回-1

        方法说明:
        使用单调栈维护已经找到但尚未确定第二个更大元素的索引
        first栈保存还没找到第一个更大元素的索引
        second栈保存已经找到第一个但还没找到第二个更大元素的索引
        """
  
        first = []  # first保存待找第一个更大的元素
        second = [] # second保存待找第二个更大的元素
        res = [-1] * len(nums)  # 初始化结果列表，默认-1表示不存在
      
        for i in range(len(nums)):
            # 处理second栈中的元素 - 当前元素nums[i]是它们的第二个更大元素
            while second and nums[second[-1]] < nums[i]:
                res[second.pop()] = nums[i]  # 记录第二个更大的元素
          
            # 处理first栈中的元素 - 当前元素nums[i]是它们的第一个更大元素
            cur = []  # 临时保存从first栈弹出的元素(这些元素找到了第一个更大元素)
            while first and nums[first[-1]] < nums[i]:
                cur.append(first.pop())  # 这些元素找到了第一个更大的nums[i]
          
            # 将找到第一个更大元素的元素转移到second栈(保持原始顺序)
            second.extend(cur[::-1])  # 逆序添加以保证顺序正确
          
            # 当前元素进入first栈(等待找到第一个更大的元素)
            first.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
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

class Solution:
    def maximumScore(self, heights: List[int], k: int) -> int:
        """
        好子数组的最大分数

        参数:
        - heights: 表示直方图每个柱子高度的列表

        返回:
        - int: 最大矩形面积

        算法思路:
        和LC84的差别在于，这里要求面积必须包含k下标
        懒计算，遇到不合群的再一次性计算前面的，因此需要前后哨兵
        使用单调栈算法，维护一个高度单调不减的柱子索引栈
        当遇到比栈顶低的柱子时，懒计算以栈顶柱子为高的矩形面积
        这里注意分清楚矩形真实的左侧和右侧 ll 和 rr 到底是啥
        然后把 kk 这个约束条件加上就可以了
        """
        
        # 首尾添加高度为0的哨兵节点:
        # 开头的0保证第一个柱子能被正确计算
        # 末尾的0保证剩余栈中的柱子能被弹出计算
        heights = [0] + heights + [0]  
        stk = []  # 存储柱子索引的单调栈（保持对应高度单调不减）
        res = 0   # 最大面积结果
        kk = k + 1 # 因为哨兵产生的移位
        
        for i, h in enumerate(heights):
            # 遇到比栈顶低的柱子时，处理所有可以被弹出的柱子
            while stk and h < heights[stk[-1]]:
                # 高度是栈顶索引所对应的高度
                hh = heights[stk.pop()]
                # 矩形实际的左侧，是栈顶下标 + 1
                # 此时的栈顶是最后一个不纳入计算面积的坐标
                ll = stk[-1] + 1
                # 矩形实际的右侧，是当前坐标 - 1
                # 因为走到了当前坐标发现不合适，当前坐标是第一个不合适的
                rr = i - 1
                if ll <= kk and kk <= rr:
                    res = max(res, hh * (rr - ll + 1))
            
            # 将当前柱子索引压入栈
            stk.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
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

class Solution:
    def maxArea(self, arr):
        """
        计算直方图中的最大矩形面积。

        参数:
        - arr: List[int]，表示直方图的高度数组。

        返回:
        - int，表示直方图中的最大矩形面积。
        """
        # 在数组两端添加哨兵元素0，简化边界条件处理
        arr = [0] + arr + [0]
        # 单调栈，存储柱子的索引
        stk = []
        n = len(arr)
        res = 0

        for i in range(n):
            # 当栈不为空且当前柱子的高度小于栈顶柱子的高度时
            while stk and arr[i] < arr[stk[-1]]:
                # 弹出栈顶柱子作为当前处理的高度
                hh = arr[stk.pop()]
                # 右边界为当前柱子的前一个位置
                rr = i - 1
                # 左边界为新的栈顶柱子的下一个位置
                ll = stk[-1] + 1
                # 更新最大面积
                res = max(res, hh * (rr - ll + 1))
            # 将当前柱子的索引入栈
            stk.append(i)
        return res

    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        """
        计算由'1'组成的最大矩形面积。

		思路: 将问题转换为多个直方图最大矩形问题： 
		1. 从第一行开始累积每列的高度（遇到'0'则重置） 
		2. 对累积后的每一行高度数组调用maxArea方法计算当前最大矩形 
		3. 最终结果是所有行中最大的矩形面积

        参数:
        - matrix: List[List[str]]，表示由'0'和'1'组成的二维矩阵。

        返回:
        - int，表示矩阵中由'1'组成的最大矩形面积。
        """
        if not matrix:
            return 0
            
        row, col = len(matrix), len(matrix[0])
        # 初始化高度数组，用于记录每一列当前连续1的高度
        arr = [0] * col 
        res = 0 

        for i in range(row):
            for j in range(col):
                # 如果是'0'则重置当前列的高度为0
                if matrix[i][j] == '0':
                    arr[j] = 0
                # 如果是'1'则增加当前列的高度
                else:
                    arr[j] += 1
            # 对每一行的高度数组计算最大矩形面积
            res = max(res, self.maxArea(arr))
        return res

 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

class Solution:
    def calByLine(self, arr):
        """
        计算以当前行为底边，所有全1子矩阵的数量。

        参数:
        - arr: List[int]，表示当前行每列的高度（连续的1的数量）

        返回:
        - int，以当前行为底边的全1子矩阵的总数
        """
        n = len(arr)
        # dp[i] 表示以第i列为右边界的所有全1子矩阵的数量
        dp = [0] * n 
        # 单调栈，用于维护递增的高度
        stk = []
        
        for i in range(n):
            # 维护单调不减栈，弹出栈顶比当前元素大的元素
            while stk and arr[i] < arr[stk[-1]]:
                stk.pop()
            # 如果栈不为空，当前列的子矩阵数为：
            # 栈顶列的dp值 + 当前高度 × (当前列与栈顶列的间隔)
            if stk:
                dp[i] = dp[stk[-1]] + arr[i] * (i - stk[-1])
            else:
                # 栈为空时，当前列的子矩阵数为：当前高度 × (当前列索引 + 1)
                dp[i] = arr[i] * (i + 1)
            # 将当前列的索引压入栈
            stk.append(i)
        # 返回所有列的子矩阵数之和
        return sum(dp)

    def numSubmat(self, mat: List[List[int]]) -> int:
        """
        计算二进制矩阵中全1子矩阵的数量。

        参数:
        - mat: List[List[int]]，输入的二进制矩阵

        返回:
        - int，全1子矩阵的总数
        """
        row, col = len(mat), len(mat[0])
        # arr 记录以当前行为底边时各列的连续1的高度
        arr = [0] * col 
        res = 0 
        
        for i in range(row):
            for j in range(col):
                # 如果当前元素是1，增加列的高度；否则重置为0
                if mat[i][j]:
                    arr[j] += 1
                else:
                    arr[j] = 0
            # 将当前行的计算结果累加到总结果中
            res += self.calByLine(arr)
        return res