描述高频题之队列&栈

栈和队列

全文概览

基础知识

栈

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:2b9d5624-bb6b-4456-9fda-0fca3898c4cf

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:b9a522ba-3a58-445b-8dc7-c648b5db30a4

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:066c5d2e-c702-4b1b-930d-2a2074d07ea9

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:d809fbd7-80b0-4707-b99e-588b347e14a6

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:30172eba-209f-473f-9be2-67dc0b255942

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:594ed762-a859-476f-a979-6ce1408e80a0

队列

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:d09c80b7-f095-477c-bfc9-5e4cc9d568c0

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:c83e8fcb-40ef-4dc2-b3c8-5931a99f39b3

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:bc44d2a0-3754-4d17-b1a8-9b2642a5a10d

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:6772dd1a-f01f-4ddb-aa0a-760586cf2363

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:8c9c4193-23b1-474b-a607-9fe5a8679d54

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:73538ec5-a415-4789-98ef-45429bdc75d3

用两个栈实现队列

剑指 Offer 09. 用两个栈实现队列

问题描述

用两个栈来实现一个队列，完成 n 次在队列尾部插入整数 (push) 和在队列头部删除整数 (pop) 的功能。 队列中的元素为 int 类型。保证操作合法，即保证pop操作时队列内已有元素。

示例：

输入：[“PSH1″,”PSH2″,”POP”,”POP”]

返回值：1,2

说明：

“PSH1″：代表将1插入队列尾部
“PSH2″：代表将2插入队列尾部
“POP”：代表删除一个元素，先进先出 => 返回1
“POP”：代表删除一个元素，先进先出 => 返回2

分析问题

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:0d8a9196-1fe5-4699-ab19-8ec27e2b64ce

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:68cdb1bc-7deb-42e8-bcb5-5b559d57a51d

1. 队列是一种先进先出的数据结构。队列中的元素是从后端入队，从前端出队。就和排队买票一样。
2. 栈是一种后进先出的数据结构。栈中的元素是从栈顶压入，从栈顶弹出。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:ee4a98d3-e2ab-44de-afd7-de2ec8c2ae86

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:ba16bb5f-2385-41d0-b091-9f9fc97df890

入队操作Push：

因为栈是后进先出的，而队列是先进先出的，所以要想使用栈来实现队列的先进先出功能，我们需要把新入栈的元素放入栈底。为了实现这个操作，我们需要先把栈S1中的元素移动到S2，接着再把新来的元素压入S2，然后再把S2中的所有元素再弹出，压入到S1。这样就实现了把新入栈的元素放入栈底的功能。

    def push(self, node):
        # write code here
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        self.stack2.append(node)
        while self.stack2:
            self.stack1.append(self.stack2.pop())

出队操作Pop:

我们直接从S1弹出就可以了，因为经过反转后，S1中的栈顶元素就是最先入栈的元素，也就是队首元素。

    def pop(self):
        if self.stack1:
            return self.stack1.pop()

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:a32a3ead-9efa-4fb4-97e2-b30a85ab720d

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:9a20c3b1-5b2a-49c7-923b-98f93ec63260

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        # write code here
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        self.stack2.append(node)
        while self.stack2:
            self.stack1.append(self.stack2.pop())

    def pop(self):
        if self.stack1:
            return self.stack1.pop()

我们可以看到入队操作的时间复杂度是O(n)，空间复杂度也是O(n)。出队时间复杂度是O(1)，空间复杂度也是O(1)。

优化

在上面的算法中，不知道你有没有发现，每次在push一个新元素时，我们都需要把S1中的元素移动到S2中，然后再从S2移回到S1中。这显然是冗余的。其实，我们在入队时只需要插入到S1中即可。而出队的时候，由于第一个元素被压在了栈S1的底部，要想实现队列的先进先出功能，我们就需要把S1的元素进行反转。我们可以把栈S1的元素Pop出去，然后压入S2。这样就把S1的栈底元素放在了栈S2的栈顶，我们直接从S2将它弹出即可。一旦 S2 变空了，我们只需把 S1 中的元素再一次转移到 S2 就可以了。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:b4e88a4a-e83f-4205-9759-c05fcd167721

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:f3927f99-0540-4df9-8d70-e395ade53a98

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        # write code here
        self.stack1.append(node)

    def pop(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

有效的括号

LeetCode 20. 有效的括号

问题描述

给定一个只包括 '('， ')'， '{'， '}'， '['， ']' 的字符串 s ，判断字符串是否有效。

有效字符满足的条件是：

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:bd3d8b9f-8b0c-499c-8ec2-eae7c2c8596e

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:8832aa28-90d9-4e64-a51c-ab8168dbc5db

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:06a8552f-c26b-4917-931b-91cf0060fb19

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:70ce749f-95a0-4eeb-9a1a-f66715ea2f97

示例：

输入：s = “()[]{}”

输出：true

分析问题

这个问题我们可以借助 “栈” 这种数据结构来解决。在遍历字符串的过程中，当我们遇见一个左括号时，我们就入栈，当我们遇到一个右括号时，我们就取出栈顶元素去判断他们是否是同类型的。如果不是的话，那就代表字符串s不是有效串，我们直接返回False。如果是，接着去遍历，直到遍历结束为止。当遍历完字符串s后，如果栈为空，就代表字符串是有效的。这里需要注意一点，为了加快判断左、右括号是否是同类型的，我们引入哈希表存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:97c97910-9f09-4f3b-8c3c-ba073083b0ae

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:ec48e55a-9a9e-4d96-95dc-14d0b18fe944

def isValid(s):
    #如果字符串不是偶数，直接返回false
    #因为字符只包含括号，所以只有偶数时才有可能匹配上
    if len(s) % 2 == 1:
        return False

    dict = {
        ")": "(",
        "]": "[",
        "}": "{",
    }

    stack = list()

    for ch in s:
        #代表遍历到右括号
        if ch in dict:
            #看栈顶元素是否能匹配上，如果没有匹配上，返回false
            if not stack or stack[-1] != dict[ch]:
                return False
            #如果匹配上，弹出栈顶元素
            stack.pop()
        else:
            #匹配到左括号，入栈
            stack.append(ch)
    #栈为空，代表s是有效串，否则是无效串
    return not stack

包含min函数的栈

剑指 Offer 30. 包含min函数的栈

问题描述

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

push(value)：将value压入栈中

pop()：弹出栈顶元素

top()：获取栈顶元素

min()：获取栈中最小元素

示例:

minStack.push(-2); -->将-2入栈
minStack.push(0);  -->将0入栈
minStack.push(-3); -->将-3入栈
minStack.min();    -->返回栈中最小元素-3
minStack.pop();    -->弹出栈顶元素-3
minStack.top();    -->返回栈顶元素0
minStack.min();    -->返回栈中最小元素-2

分析问题

对于普通的栈来说，执行push和pop的时间复杂度是O(1)，而执行min函数的时间复杂度是O(N)，因为要想找到最小值，就需要遍历整个栈，为了降低min函数的时间复杂度，我们引入了一个辅助栈。

• 数据栈A：栈A用来存储所有的元素，保证入栈push、出栈pop、获取栈顶元素top的操作。
• 辅助栈B：栈B用来存储栈A中所有 非严格递减的元素，即栈A中的最小值始终在栈B的栈顶，这样可以保证以O(1)的时间复杂度来返回栈中的最小值。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:59bcebac-e58f-482e-a6ec-60f2b20e090b

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:3a6fed04-af95-48dc-b0f7-99a35821b65b

class Solution:
    def __init__(self):
        #数据栈
        self.A = []
        #辅助栈
        self.B = []
    #push操作
    def push(self, x):
        self.A.append(x)
        #如果辅助栈B为空，或者栈顶元素大于x，则入栈
        if not self.B or self.B[-1] >= x:
            self.B.append(x)

    def pop(self):
        #弹出数据栈A中的元素
        s = self.A.pop()
        #如果弹出的元素和栈B的栈顶元素相同，则为了保持一致性
        #将栈B的栈顶元素弹出
        if s == self.B[-1]:
            self.B.pop()

    def top(self):
        #返回数据栈A中的栈顶元素
        return self.A[-1]

    def min(self):
        #返回辅助栈B中的栈顶元素
        return self.B[-1]

表达式求值

问题描述

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:b603a8a2-085d-4eeb-a93c-1dc928017161

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:28b45fb9-6df3-4588-9706-d59adbb1af7b

示例：

输入：”（2 * （3 – 4）））* 5″

返回值：-10

分析问题

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:2cca7d91-f2ac-4204-81c2-6d4f487f3277

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:2b965063-a7af-4eea-b0dd-419f403cd542

遍历字符串s，并用变量preSign记录每个数字之前的运算符，初始化为加号。

1. 遇到空格时跳过。
2. 遇到数字时，继续遍历求出这个完整的数字的值，保存到num中。
3. 遇到左括号时，需要递归的求出这个括号内的表达式的值。
4. 遇到运算符或者表达式的末尾时，就根据上一个运算符的类型来决定计算方式。
5. 如果是加号，不需要进行计算，直接push到栈里
6. 如果是减号，就去当前数的相反数，push到栈里
7. 如果是乘号，就需要从栈内pop出一个数和当前数求乘法，再把计算结果push到栈中
8. 最后把栈中的结果求和即可。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:d6b26f8b-ce7d-419b-abbb-18494948c6d4

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:bb252c40-7e56-4cd2-8fed-7e0062779765

class Solution:
    def calculate(self, s):
        n = len(s)
        #存取部分数据和
        stack = []
        preSign = '+'
        num = 0
        i=0
        while i<n: 10 c="s[i]" if ': i="i+1" continue c.isdigit(): num="num" * + ord(c) - ord('0') #如果遇到左括号，递归求出括号内表达式的值 j="i+1" counts="1" #截取出括号表达式的值 while>0:
                    if s[j]=="(":
                        counts=counts+1
                    if s[j]==")":
                        counts=counts-1
                    j=j+1
                #&#x5265;&#x53BB;&#x4E00;&#x5C42;&#x62EC;&#x53F7;&#xFF0C;&#x6C42;&#x62EC;&#x53F7;&#x5185;&#x8868;&#x8FBE;&#x5F0F;&#x7684;&#x503C;
                num=self.calculate(s[i+1:j-1])
                i=j-1

            if not c.isdigit() or i==n-1:
                if preSign=="+":
                    stack.append(num)
                elif preSign=="-":
                    stack.append(-1*num)
                elif preSign=="*":
                    tmp=stack.pop()
                    stack.append(tmp*num)

                num=0
                preSign=c
            i=i+1
        return sum(stack)

s=Solution()
print(s.calculate("(3+4)*(5+(2-3))"))
</n:>

滑动窗口的最大值

LeetCode 239. 滑动窗口最大值

问题描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

示例：

输入：[2，3，4，2，6，2，5，1]，3

输出：[4，4，6，6，6，5]

分析问题

这道题的关键点在于求滑动窗口中的最大值。大小为k的滑动窗口，我们可以通过遍历的方式来求出其中的最大值，需要O(k)的时间复杂度。对于大小为n的数组nums，一共有n-k+1个窗口，因此该算法的时间复杂度是O(nk)。

通过观察，我们可以知道，对于两个相邻的滑动窗口，有k-1个元素是共用的，只有一个元素是变化的，因此我们可以利用此性质来优化我们的算法。

对于求最大值问题，我们可以使用优先级队列（大顶推）来求解。首先，我们将数组的前k个元素放入优先级队列中。每当我们向右移动窗口时，我们就可以把一个新的元素放入队列中，此时堆顶元素就是堆中所有元素的最大值，然而这个最大值有可能不属于当前的滑动窗口中，我们需要将该元素进行移除处理（如果最大值不在当前滑动窗口中，它只能在滑动窗口的左边界的左侧，所以滑动窗口向右移动的过程中，该元素再也不会出现在滑动窗口中了，所以我们可以对其进行移除处理）。我们不断地移除堆顶的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。

为了方便判断堆顶元素与滑动窗口的位置关系，我们可以在优先队列中存储二元组 （num，index），表示元素num在数组中的下标为index。

小trick：因为python中只提供了小顶堆，所以我们需要对元素进行取反处理，例如对于列表[1, -3]，我们对元素进行取反，然后插入小顶堆中，此时堆中是这样的[-1,3]，我们取出堆顶元素-1，然后取反为1，正好可以得到列表中的最大值1。

我们nums=[2，3，4，2，6，2，5，1]，k=3为例，来看一下具体的过程。

1. 首先，我们将nums的前3个元素放入优先级队列中，队首元素下标值index=2>0，在窗口中，所以加入结果中，此时res=[4]。
2. 下一个元素2入队，此时队首元素下标index=2>1，在窗口中，所以加入结果中，此时res=[4,4]。
3. 下一个元素6入队，此时队首元素下标index=4>2，在窗口中，所以加入结果中，此时res=[4,4,6]。
4. 下一个元素2入队，此时队首元素下标index=4>3，在窗口中，所以加入结果中，此时res=[4,4,6,6]。
5. 下一个元素5入队，此时队首元素下标index=4=4，在窗口中，所以加入结果中，此时res=[4,4,6,6,6]。
6. 下一个元素1队列，此时队首元素下标index=4

进阶

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:b76b39fa-8201-4a7f-9524-c07814d590d5

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:f5b3a24c-223e-4a50-899e-2871adeddcbb

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:add0fc21-7eea-4963-8a15-b81ad6a95313

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:b7abfde3-5369-473e-98ab-bdea85629105

我们还是以nums=[2，3，4，2，6，2，5，1]，k=3为例，来看一下具体的过程。我们首先初始化一个空队列que。

1. 此时队列为que空，元素2对应的下标0入队。并且此时未形成窗口，不取值。
2. 此时队列que=[0]，队尾元素为0，它对应数组中的元素是nums[0] < nums[1]的，所以我们把队尾0弹出，此时队列为空，我们将1入队。并且此时未形成窗口，不取值。
3. 此时队列que=[1]，队尾元素为1，它对应的数组中的元素是nums[1] < nums[2]的，所以我们把队尾1弹出，此时队列为空，我们将2入队。并且此时队首元素2在窗口[0,2]中，所以取出队首元素。
4. 此时队列que=[2]，队尾元素为2，它对应的数组中的元素是nums[2] > nums[3]的，所以我们将3入队。并且此时队首元素2在窗口[1,3]中，所以取出队首元素。
5. 此时队列que=[2,3]，队尾元素为3，它对应的数组中的元素是nums[3] < nums[4]的，所以我们把队尾3弹出，并且此时队尾元素对应的数组中的元素是nums[2] < nums[4]，所以我们把队尾2弹出，此时队列为空，我们将4入队。并且此时队首元素4在窗口[2,4]中，所以取出队首元素。
6. 此时队列que=[4]，队尾元素为4，它对应的数组中的元素是nums[4] > nums[5]的，所以我们将5入队。并且此时队首元素4在窗口[3,5]中，所以我们取出队首元素。
7. 此时队列que=[4，5]，队尾元素为5，它对应的数组中的元素是nums[5] < nums[6]的，所以我们把队尾5弹出，此时队尾元素对应的数组中的元素时nums[4] > nums[6] ，所以我们将6入队。并且此时队首元素4在窗口[4，6]中，所以我们取出队首元素。
8. 此时队列que=[4，6]，队尾元素为6，它对应的数组中的元素是nums[6] > nums[7]的，所以我们将7入队。而此时队首元素4不在窗口[5,7]中，所以我们将其移除队列，此时队首元素6在窗口[5,7]中，所以我们将其取出。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:d16f9ca8-0ab8-4610-865e-eca3b65f5f37

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:c4ee97b1-2f60-4341-a110-e71addce7484

import collections
class Solution:
    def maxSlidingWindow(self, nums, k):
        n = len(nums)
        #申请一个双端队列
        q = collections.deque()

        #初始化第一个窗口
        for i in range(k):
            #如果队列不为空且比队尾元素大，将队尾出队
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            #直到队列为空，或者比队尾元素小，入队
            q.append(i)

        #将队首元素加入结果中
        ans = [nums[q[0]]]

        #窗口逐步向右移动
        for i in range(k, n):
            #如果队列不为空且比队尾元素大，将队尾出队
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            #直到队列为空，或者比队尾元素小，入队
            q.append(i)
            #如果队首元素不在该窗口内，出队操作
            while q[0] <= i - k: q.popleft() #将队首元素加入结果中 ans.append(nums[q[0]]) return ans s="Solution()" print(s.maxslidingwindow([2,3,4,2,6,2,5,1],3)) < code></=>

栈和排序

问题描述

给你一个由1~n，n个数字组成的一个排列和一个栈，要求按照排列的顺序入栈。如何在不打乱入栈顺序的情况下，仅利用入栈和出栈两种操作，输出字典序最大的出栈序列。

排列：指 1 到 n 每个数字出现且仅出现一次。

示例：

输入：[2,4,5,3,1]

输出：[5,4,3,2,1]

分析问题

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:28394654-fa21-403a-8ded-6cde6f9b1672

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:028b2807-66ab-4bbd-9cb1-29b2286ba69c

为了快速判断”当前入栈元素是否大于之后将要入栈的元素”，我们需要创建一个辅助数组temp，其中temp[i]表示i之后的最大元素。借助辅助数组，我们可以以O(1)的时间复杂度去判断当前入栈元素是否大于之后将要入栈的元素。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:4cf4b696-ecf7-4df3-b129-24a9eb481a0d

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:7e4ef959-b02a-4cfa-98bf-4c2eff284233

import sys
class Solution:
    def solve(self , a):
        n=len(a)
        res=[]
        if n==0:
            return res
        stack=[]
        temp=[0]*n
        temp[n-1]=-sys.maxsize-1
        #从右往左遍历数组a,然后取填充temp
        #使得temp[i]表示i之后的最大元素
        for i in range(n-2,-1,-1):
            temp[i]=max(a[i+1],temp[i+1])

        #遍历数组a
        for i in range(0,n):
            if a[i] > temp[i]:  #若当前元素大于之后将要入栈的元素,将其加入结果中
                res.append(a[i])
                # 若栈不为空，且栈顶元素大于temp[i],
                # 栈顶出栈，加入结果中
                while stack and stack[-1] > temp[i]:
                    res.append(stack[-1])
                    stack.pop()
            else:
                stack.append(a[i])

        while stack:
            res.append(stack[-1])
            stack.pop()
        return res

该算法的时间复杂度是O(n)，空间复杂度也是O(n)。

单调栈

问题描述

给定一个长度为 n 的可能含有重复值的数组 arr ，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。请设计算法，返回一个二维数组，表示所有位置相应的信息。位置信息包括：两个数字 l 和 r，如果不存在，则值为 -1，下标从 0 开始。

示例：

输入：[3,4,1,5,6,2,7]

输出：[[-1,2],[0,2],[-1,-1],[2,5],[3,5],[2,-1],[5,-1]]

分析问题

这道题最简单的解法就是暴力求解，即通过两层for循环来求解。如下所示：

class Solution:
    def foundMonotoneStack(self , nums):
        n=len(nums)
        res=[]
        #遍历一遍数组
        for i in range(0,n):
            l=-1
            r=-1
            #从左往右寻找l，寻找比nums[i]小的最近的nums[l]
            for j in range(0,i):
                if nums[j] < nums[i]:
                    l=j

            #&#x4ECE;&#x53F3;&#x5F80;&#x5DE6;&#x5BFB;&#x627E;l&#xFF0C;&#x5BFB;&#x627E;&#x6BD4;nums[i]&#x5C0F;&#x7684;&#x6700;&#x8FD1;&#x7684;nums[r]
            for j in range(n-1,i,-1):
                if nums[j] < nums[i]:
                    r=j

            res.append([l,r])
        return res

该算法的时间复杂度是O(n^2)，空间复杂度是O(1)。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:1a18e72e-675a-4df7-8187-b28ad141cdf7

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:d6dac039-a742-4a99-bb43-a50f68354fc0

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:2f53ca59-ee86-4385-9bf6-0caa9e7255bc

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:afe44b89-69b3-49da-bd37-e9ecc965170a

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:9f3e760d-1326-4aa6-afc6-5c4fcdfab055

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:7e0509a1-8f56-49a8-81f8-08e9d9d2bc78

我们以 求每一个i左边离i最近且小于arr[i]的位置为例，来看一下算法的执行流程。首先我们从左往右遍历数组。

• 假设遍历到的元素是 arr[i]，栈顶元素 top 对应的数组中的元素是 arr[top]，然后我们拿 arr[i] 和 arr[top] 进行对比。
• 如果 arr[top] > arr[i]，就说明 top 不是第 i 个元素的解，也不会是 i 以后任何元素的解（因为 i 比 top 距离后面的数更近，同时arr[i] < arr[top]），所以我们就把top弹出，直到栈为空或者栈顶元素（数组的下标）对应数组中的元素小于 arr[i]。
• 如果arr[top] < arr[i]，就说明第 i 个数的解就是 top，因为栈内的元素都是单调递增的，所以 top 是离 i 最近的数，即 top 就是所求值。然后因为 i 可能是 i 右侧的候选解，所以把 i 加入栈中。

同理，我们从右往左遍历数组，就可以得到 每一个i右边离i最近且小于arr[i]的位置。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:1eb53af2-0efc-4f66-873e-c35617dc766e

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:3e9af086-89ab-494e-82a4-86e767d4531a

class Solution:
    def foundMonotoneStack(self , nums):
        n=len(nums)
        res=[]
        l=[0]*n
        r=[0]*n
        #单调栈
        stack=[]
        #从左往右遍历数组
        for i in range(0,n):
            #如果栈顶元素top对应的数组中的元素num[top]>nums[i]
            #则出栈，直到栈为空或者栈顶元素对应的数组中的元素比nums[i]小
            while stack and nums[stack[-1]] >=nums[i]:
                stack.pop()

            l[i]=stack[-1] if stack else -1
            #i入栈，因为i有可能成为i右边的答案
            stack.append(i)

        stack=[]
        #从右往左遍历数组
        for i in range(n-1,-1,-1):
            # 如果栈顶元素top对应的数组中的元素num[top]>nums[i]
            # 则出栈，直到栈为空或者栈顶元素对应的数组中的元素比nums[i]小
            while stack and nums[stack[-1]] >= nums[i]:
                stack.pop()
            r[i] = stack[-1] if stack else -1
            # i入栈，因为i有可能成为i左边的答案
            stack.append(i)

        for i in range(0,len(l)):
            res.append([l[i],r[i]])

        return res

s=Solution()
print(s.foundMonotoneStack([3,4,1,5,6,2,7]))

该算法的时间复杂度是O(n)，空间复杂度是O(n)。

每日温度

739. 每日温度

问题描述

请根据每日气温列表 temperatures ，计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例：

输入：temperatures = [73,74,75,71,69,72,76,73]

输出：[1,1,4,2,1,1,0,0]

分析问题

既然是求每一天需要等几天才会有更高的温度，那么最直观的想法就是针对气温列表 temperatures 中的每个温度值，向后依次进行搜索，找到第一个比当前温度更高的值的位置索引，然后减去当前温度所在的位置索引，就是要求的结果。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:d4651642-d01d-4366-b515-56bf14713c0d

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:7ecc788a-760a-4ce9-873a-b84ae9e52249

class Solution(object):
    def dailyTemperatures(self,temperatures):
        #求出温度列表的长度
        n = len(temperatures)
        result=[0]*n
        #遍历每一个温度值
        for i in range(n):
            if temperatures[i]<100: #想后搜索第一个大于当前温度值的元素 for j in range(i+1,n): if temperatures[j]> temperatures[i]:
                        result[i]=j-i
                        break

        return result
</100:>

该算法的时间复杂度是O(n^2)，空间复杂度是O(n)。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:b0060836-7080-4b67-a80d-f178ca4d707e

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:b1760efa-efff-4549-8346-64b55da2e3f6

优化

这里可以使用单调栈来优化，即维护一个温度值下标的单调栈，使得从栈顶到栈底的的元素对应的温度值依次递减。具体来说，我们正向遍历温度列表 temperatures。对于温度列表中的每个元素 temperatures[i]。如果栈为空，则直接将 i 进栈；如果栈不为空，则比较栈顶元素 prev 对应的温度值 temperatures[prev] 和 当前温度 temperatures[i]。

• 如果 temperatures[prev] < temperatures[i]，则将栈顶元素 prev 移除，此时 prev 对应的等待天数为 i – prev。重复上述操作直到栈为空或者栈顶元素对应的温度大于等于当前温度，然后将 i 进栈。
• 如果 temperatures[prev] > temperatures[i]，则直接将元素 i 入栈。

下面我们来思考一个问题，为什么可以在出栈的时候更新等待天数 result[prev] 呢？因为即将进栈的元素 i 对应的温度值 temperatures[i] 一定是 temperatures[prev] 右边第一个比它大的元素。

下面我们来看一个具体的例子，假设温度列表 temperatures = [73,74,75,71,69,72,76,73] 。

初始时，单调栈 stack 为空；等待天数 result 为 [0,0,0,0,0,0,0,0]。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:317b17e0-c0c6-40a8-9225-ae76c6c98216

[En]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:7b7f86ec-a37b-473a-a5d3-aaa0ba5bbe98

n = len(temperatures)
        #初始化一个空的栈
        stack = []
        result = [0] * n
        for i in range(n):
            temperature = temperatures[i]
            #如果 temperatures[i] 大于栈顶元素对应的温度值，则栈顶元素出栈。
            while stack and temperature > temperatures[stack[-1]]:
                prev = stack.pop()
                result[prev] = i - prev
            stack.append(i)
        return result

该算法的时间复杂度是O(n)，空间复杂度也是O(n)。

Original: https://www.cnblogs.com/cxyxz/p/15623259.html
Author: 算法推荐管
Title: 描述高频题之队列&栈