由于有四种情况的单调栈，为了不容易出错，我决定全部转换成「求左边第一个比自己小的」单调栈
0X00 模板
求左边第一个比自己小的 模板
def make(a):
n = len(a)
ans = [float("inf")] * n
stack = []
for i, v in enumerate(a):
while stack and stack[-1] >= v: stack.pop()
if stack: ans[i] = stack[-1]
stack.append(v)
return ans
- 如果求左边第一个比自己大的，就把原数组取负
- 如果求右边第一个比自己小的，就把原数组取反，最后一定要思考是不是要反过来
- 如果求右边第一个比自己大的，就把原数组取反，再全部取负数，最后也一定要思考是不是要反过来
0X01 引申
求左边比自己大的里面最小的
我们把原数组的下标按照值按降序排序，然后左边第一个下标比自己小的就是「左边比自己大的里面最小的」
class Solution:
def oddEvenJumps(self, A: List[int]) -> int:
def make(a):
stack, res = [], [None] * n
for _, v in enumerate(a):
while stack and stack[-1] > v: stack.pop()
if stack: res[v] = stack[-1]
stack.append(v)
return res
n, A = len(A), A[::-1]
B = sorted(range(n), key=lambda i: -A[i])
oddprev = make(B)
B = sorted(range(n), key=lambda i: A[i])
evenprev = make(B)
odd, even = [False] * n, [False] * n
odd[0] = even[0] = True
for i in range(1, n):
if oddprev[i] != None:
odd[i] = even[oddprev[i]]
if evenprev[i] != None:
even[i] = odd[evenprev[i]]
return sum(odd)
求左边比自己小的最大的
把原数组的下标按升序排序，然后左边第一个下标比自己小的就是「左边比自己小的最大的」
0X02 相关题目
注意判断尽量使用 != None
网友评论