题目描述
给一个数组nums，数组是循环的，求每个元素的下一个元素
| f1-xxx |
基本分析
- 循环数组的情况怎么考虑？拉直或者下标取余数
- 剩下怎么解决？常见的单调递减栈
代码
左到右
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
n = len(nums)
ls = nums * 2
st = []
right = [-1] * 2 * n
for i in range(2*n):
while st and ls[i] > ls[st[-1]]:
top = st.pop()
right[top] = ls[i]
st.append(i)
return right[:n]
右到左
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
n = len(nums)
ls = nums * 2
st = []
right = [-1] * 2 * n
for i in range(2 * n-1, -1, -1):
while st and ls[i] >= ls[st[-1]]:
st.pop()
if st:
right[i] = ls[st[-1]]
st.append(i)
return right[:n]
总结
- 处理循环数组时候的方法