算法练习知识

单调栈

单调栈是一个特殊的栈，栈内元素是单调递增或单调递减的。单调栈的应用场景主要是解决一些区间问题，比如求区间内的最大值、最小值等。

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.append(-1)
        n = len(heights)
        ans = 0
        s = []
        for r in range(n):
            while s and heights[r] <= heights[s[-1]]:
                h = s[-1]
                s.pop()
                l = s[-1] if s else -1
                ans = max(ans , ( r - l - 1) * heights[h])
            s.append(r)
        return ans

Leetcode Hard

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

class Solution:
    def findMedianSortedArrays(self, a: List[int], b: List[int]) -> float:
        if len(a) > len(b):
            a, b = b, a  # 保证下面的 i 可以从 0 开始枚举

        m, n = len(a), len(b)
        a = [-inf] + a + [inf]
        b = [-inf] + b + [inf]

        # 枚举 nums1 有 i 个数在第一组
        # 那么 nums2 有 j = (m + n + 1) // 2 - i 个数在第一组
        i, j = 0, (m + n + 1) // 2
        while True:
            if a[i] <= b[j + 1] and a[i + 1] > b[j]:  # 写 >= 也可以
                max1 = max(a[i], b[j])  # 第一组的最大值
                min2 = min(a[i + 1], b[j + 1])  # 第二组的最小值
                return max1 if (m + n) % 2 else (max1 + min2) / 2
            i += 1  # 继续枚举
            j -= 1