单调栈,单调队列

小半 • 2023年2月2日下午6:23 • 技术随笔 • 阅读 172

单调栈

题目描述:带有最小功能函数的栈 O(1)

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

解法

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack ,self.min_ = [] ,[]
        

    def push(self, x: int) -> None:
        if not self.min_ or self.min_[-1] >= x:#不是严格大于的,不然容易无#法处理同最小值
            self.min_.append(x)
        self.stack.append(x)

    def pop(self) -> None:
        if self.stack.pop() == self.min_ [-1]:
            self.min_.pop()

    def top(self) -> int:
        return self.stack[-1]

    def min(self) -> int:
        return self.min_[-1]
总结:

如果只使用一个变量来标记最小值,那么必然产生一个问题就是最小值一旦出栈,那么没办法找到第二小的值,所以最小值需要有记忆特性. 那么就使用栈.但是栈不是严格递增的,因为最小值相同的时候,(存在不止一个相同的最小值,如,两个0都是最小值),一旦其中一个最小值出栈,那么就造成存最小值的栈中没有对应的最小值.

单调队列:

题目描述:给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        #单调队列
        #未形成窗口之前
        if not nums or k == 0: return []
        queue_ = collections.deque()
        for i in range (k):
            while  queue_ and queue_[-1] < nums[i]:
                queue_.pop()
            queue_.append(nums[i])
        res = [queue_[0]]
        #形成了窗口
        n = len(nums)
        for i in range(k,n):
            if queue_[0] == nums[i-k]:
                queue_.popleft()
            while queue_ and queue_[-1] < nums[i]:
                queue_.pop()
            queue_.append(nums[i])
            res.append(queue_[0])
        return res

解题思路:

因为是滑动窗口,所以对应的是双端队列,关于python中的双端队列使用的是collection.deque(),其可以直接popleft().本题使用单调队列的形式来处理.queue_是一个非严格递减的排序队列.在形成窗口之前与形成窗口之后的差异在于形成窗口之后,随着窗口移动,在queue_中的元素,可能正好从滑动窗口中删除了.所以需要加以判断