日拱两卒（三）

80#

划分字母区间。

把一个字符串分成尽可能多的区间，同一种字母必须出现在同一个区间。

预处理出来每个字母的最左和最右。

从前往后扫，维护必须延伸到的最右边。

1
class Solution:
2
    def partitionLabels(self, s: str) -> List[int]:
3
        n = len(s)
4
        seg = [[-1] * 2 for _ in range(26)]
5

6
        for i, ch in enumerate(s):
7
            idx = ord(ch) - ord('a')
8
            if seg[idx][0] == -1:
9
                seg[idx][0] = i
10
            seg[idx][1] = i
11

12
        ans = []
13
        l = 0
14
        r = seg[ord(s[0]) - ord('a')][1]
15
        i = l
16
        while True:
17
            if r >= n - 1:
18
                ans.append(n - 1 - l + 1)
19
                break
20
            if i > r:
21
                ans.append(r - l + 1)
22
                l = i
23
                r = seg[ord(s[i]) - ord('a')][1]
24

25
            r = max(r, seg[ord(s[i]) - ord('a')][1])
26
            i += 1
27

28
        return ans

79#

跳跃游戏II。

问在nums上从0跳到n - 1的最小次数。每一次可以跳0到nums[i]之间任意远。

记忆化做法在Leetcode上没被卡。

但本质上和80 划分字母区间是同一道题。

维护当前区间的最远延申位置，每当指针越过这个边界，就完成一次切割或者跳跃。

1
class Solution:
2
    def jump(self, nums: List[int]) -> int:
3
        n = len(nums)
4
        if n == 1:
5
            return 0
6

7
        right = [i + nums[i] for i in range(n)]
8

9
        ans = 0
10
        r = right[0]
11
        max_r = r
12
        i = 0
13

14
        while True:
15
            if r >= n - 1:
16
                ans += 1
17
                break
18

19
            if i > r:
20
                ans += 1
21
                r = max_r
22
                continue
23

24
            max_r = max(max_r, right[i])
25
            i += 1
26

27
        return ans

78#

跳跃游戏。

上一题的Easy版，只问能否跳到，而不问最小跳跃次数。

1
class Solution:
2
    def canJump(self, nums: List[int]) -> bool:
3
        n = len(nums)
4
        r = 0
5
        for i in range(n):
6
            r = max(r, i + nums[i])
7
            if i >= r and r != n - 1:
8
                return False
9
        return True

77#

买卖股票的最佳时机。

知道每一天的股票价格，问最大可能利润。简单贪心。

1
class Solution:
2
    def maxProfit(self, prices: List[int]) -> int:
3
        n = len(prices)
4

5
        rmax = [0] * (n + 1)
6
        rmax[n] = 0
7
        for i in range(n - 1, -1, -1):
8
            rmax[i] = max(rmax[i + 1], prices[i])
9

10
        ans = 0
11
        for i in range(n):
12
            ans = max(ans, rmax[i] - prices[i])
13
        return ans

76#

数据流的中位数。

往列表里不断添加元素，每添加一个元素就打印当前列表的中位数。

维护对顶堆，一个最大堆存前一半元素，一个最小堆存后一半元素，中位数只会与两个堆顶相关。

Python里有内置的堆相关内置函数，heappush是按堆的方式插元素，heappushpop是插完一个后再弹出堆顶。

默认是最小堆，想用最大堆就存相反数。

1
class MedianFinder:
2

3
    def __init__(self):
4
        self.left = []
5
        self.right = []
6

7
    def addNum(self, num: int) -> None:
8
        if len(self.left) == len(self.right):
9
            add_to_left = heappushpop(self.right, num)
10
            heappush(self.left, -add_to_left)
11
        else:
12
            add_to_right = heappushpop(self.left, -num)
13
            heappush(self.right, -add_to_right)
14

15
    def findMedian(self) -> float:
16
        if len(self.left) > len(self.right):
17
            return -self.left[0]
18
        return (-self.left[0] + self.right[0]) / 2

75#

前 K 个高频元素。

哈希加桶排序。

1
class Solution:
2
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
3
        cnt = {}
4
        for num in nums:
5
            cnt[num] = cnt.get(num, 0) + 1
6
        max_cnt = max(cnt.values())
7

8
        buckets = [[] for _ in range(max_cnt + 1)]
9
        for x, c in cnt.items():
10
            buckets[c].append(x)
11

12
        ans = []
13
        for bucket in reversed(buckets):
14
            ans += bucket
15
            if len(ans) == k:
16
                return ans

74#

数组中的第K大元素。

快速排序的思想+每次丢掉一半。

Python里写成这种三路归并的方法应该最好理解。

处理完有[l, lt - 1] < pivot, [lt, gt] = pivot, [gt + 1, r] > pivot。

1
class Solution:
2
    def quick_select(self, q, l, r, k) -> int:
3
        if l >= r:
4
            return q[l]
5

6
        pivot = q[random.randint(l, r)]
7

8
        lt, i, gt = l, l, r
9
        while i <= gt:
10
            if q[i] < pivot:
11
                q[i], q[lt] = q[lt], q[i]
12
                lt += 1
13
                i += 1
14
            elif q[i] > pivot:
15
                q[i], q[gt] = q[gt], q[i]
16
                gt -= 1
17
            else:
18
                i += 1
19

20
        if k < lt - l:
21
            return self.quick_select(q, l, lt - 1, k)
22
        if k <= gt - l:
23
            return pivot
24
        return self.quick_select(q, gt + 1, r, k - (gt - l + 1))
25

26

27
    def findKthLargest(self, nums: List[int], k: int) -> int:
28
        n = len(nums)
29
        return self.quick_select(nums, 0, n - 1, n - k)

73#

柱状图重最大的矩形。

枚举高，单调栈算左右最长能延申到哪。

1
class Solution:
2
    def largestRectangleArea(self, h: List[int]) -> int:
3
        ans = 0
4
        n = len(h)
5

6
        stack = []
7
        l = [-1] * n
8
        for i in range(n):
9
            while(stack and h[stack[-1]] >= h[i]):
10
                stack.pop()
11
            if stack:
12
                l[i] = stack[-1]
13
            stack.append(i)
14

15
        stack = []
16
        r = [n] * n
17
        for i in range(n - 1, -1, -1):
18
            while(stack and h[stack[-1]] >= h[i]):
19
                stack.pop()
20
            if stack:
21
                r[i] = stack[-1]
22
            stack.append(i)
23

24

25
        for i in range(n):
26
            ans = max(ans, h[i] * ((r[i] - 1) - (l[i] + 1) + 1))
27

28
        return ans

72#

每日温度。

给定每一天温度，问每一天的下一个更高温度出现在几天后。

找右边第一个更大的数，单调栈经典应用。

1
class Solution:
2
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
3
        n = len(temperatures)
4
        ans = [0] * n
5
        stack = []
6

7
        for i in range(n - 1, -1, -1):
8
            while stack and temperatures[stack[-1]] <= temperatures[i]:
9
                stack.pop()
10
            if stack:
11
                ans[i] = stack[-1] - i
12
            stack.append(i)
13

14
        return ans

71#

字符串解码。

3[a]2[2[bc]]解析成aaabcbcbcbc。

简单递归模拟。

1
class Solution:
2
    def decodeString(self, s: str) -> str:
3
        if not s:
4
            return s
5

6
        if s[0].isalpha():
7
            return s[0] + self.decodeString(s[1:])
8

9
        i = s.find('[')
10
        n = len(s)
11
        left = 1
12
        for j in range(i + 1, n):
13
            if s[j] == '[':
14
                left += 1
15
            elif s[j] == ']':
16
                left -= 1
17
                if left == 0:
18
                    return self.decodeString(s[i+1:j] * int(s[:i])) + self.decodeString(s[j+1:])