程序员代码面试指南之单调栈结构

题目来《程序员代码面试指南》第2版，作者左程云。

对于一个数组（可能有重复元素），对于每个元素arr[i]，找到它左边和右边小于arr[i]且离i最近的元素下标，找不到时返回-1。书中为了克服相同元素带来的麻烦，使用了一个stack<list>，其实不需要，stack<int>即可。

分析：利用一个非递减的单调栈（即允许重复元素的递增栈）。对于任意两个元素arr[j]，arr[k]，如果j<k，那么如果arr[j]>arr[k]，那么对于k及k右边的任意元素，j都不可能是他们的左边界。所以栈里面只需保存左边比自己小的元素，且越往左越小。每个元素arr[i]即将入栈时即可确定它的左边界，如果栈顶元素小于arr[i]，那么arr[i]的左边界就是栈顶元素；如果栈顶元素等于arr[i]，那么arr[i]的左边界就是栈顶元素的左边界。每个元素弹出的时候即可确定它的右边界，右边界就是即将入栈的那个元素。如果元素最终没有被弹出，说明右边没有比它更小的元素了，那么它的右边界就是默认值-1，这样书中代码最后一部分清空栈的操作也是不需要的了。(书里的代码是在弹出元素的时候同时确定它的左边界和右边界，右边界就是即将入栈的元素，左边界就是弹出后的栈顶元素。）

代码如下：

def getNearLess(arr):
    n = len(arr)
    result = [[-1,-1] for i in range(n)]
    stack = []
    for i in range(n):
        while stack and arr[stack[-1]] > arr[i]:
            popIndex = stack.pop()
            result[popIndex][1] = i
        if stack:
            if arr[stack[-1]] == arr[i]:
                result[i][0] = result[stack[-1]][0]
            else:
                result[i][0] = stack[-1]
        stack.append(i)
    return result
    
print(getNearLess([3,1,3,4,3,5,3,2,2]))

def bruteForce(arr):
    n = len(arr)
    result = [[-1,-1] for i in range(n)]
    stack = []
    for i in range(n):
        for j in range(i-1, -1, -1):
            if arr[j] < arr[i]:
                result[i][0] = j
                break
        for j in range(i+1, n):
            if arr[j] < arr[i]:
                result[i][1] = j
                break
    return result

import random
run = 1000
for i in range(run):
    arr = [random.randint(1,5) for i in range(10)]
    assert bruteForce(arr) == getNearLess(arr)