题解 | #单调栈#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int一维数组 
# @return int二维数组
#
class Solution:
    def foundMonotoneStack(self , nums ):
        # write code here
        if nums == []:
            return
        # 初始化
        n = len(nums)
        ret = [[-1, -1] for _ in range(n)]
         
        # 从左往右，寻找右侧min,每个元素入栈，对比后一个元素是否小于它，
        #小于则修改对应ret的值，并弹出该元素，比较前一个元素与该值的大小，最后，将该元素加入栈
        stack = []
        for i in range(n):
            # 如果不满足单调性
            while stack and nums[stack[-1]] > nums[i]:
                ret[stack.pop()][1] = i
            # 入栈
            stack.append(i)
        # 从右往左，寻找左侧min
        stack = []
        for i in range(n - 1, -1, -1):
            # 如果不满足单调性
            while stack and nums[stack[-1]] > nums[i]:
                ret[stack.pop()][0] = i
            # 入栈
            stack.append(i)
        # 返回结果
        return ret
                
#         res = []
#         for i in range(len(nums)):
#             r = []
#             for j in range(i-1, -1, -1):
#                 if nums[i] > nums[j]:
#                     r.append(j)
#                     break
#             else:
#                 r.append(-1)
#             for x in range(i+1, len(nums)):
#                 if nums[x] < nums[i]:
#                     r.append(x)
#                     break
#             else:
#                 r.append(-1)
#             res.append(r)
#         return res