单调栈结构

题目

给定一个不含有重复值的数组arr，找到每一个i位置左边和右边离i位置最近且值比arr[i]小的位置。返回所有位置相应的信息。

类似题目：132模板https://leetcode-cn.com/problems/132-pattern/

-1表示不存在。
要求：时间复杂度：O(n)

解答

单调栈：指栈内元素都是严格单调递增或者单调递减的。
如果有新元素入栈，栈调整过程中会破坏所有单调性的栈顶元素出栈，并且出栈的元素不会再次入栈。
由于每个元素只有一次入栈和出栈的操作，所以单调栈的维护时间复杂度是O(n)。

单调栈的性质：

• 单调栈里的元素具有单调性；
• 递减栈（从栈顶到栈底递减）中可以找到元素左右两侧比自身大的第一个元素
• 同理，递增栈有相似的性质

本题实现O(n^2)很简单，每个位置分别向左向右遍历。

思考：如果优化，做到时间复杂度O(n)。

代码

def getNearlessNoRepeat(arr):
    ans = [None] * len(arr)
    stack = []
    for i in range(len(arr)):
        while stack and arr[stack[-1]] > arr[i]:
            popIndex = stack.pop()
            if len(stack) == 0:
                leftLessIndex = -1
            else:
                leftLessIndex = stack[-1]
            ans[popIndex] = (leftLessIndex, i)
        stack.append(i)
    while len(stack) > 0:
        popIndex = stack.pop()
        if len(stack) == 0:
            leftLessIndex = -1
        else:
            leftLessIndex = stack[-1]
        ans[popIndex] = (leftLessIndex, -1)
    return ans
arr = [3, 4, 1, 5, 6, 2, 7]
print(getNearlessNoRepeat(arr))