一.问题介绍

在排序数组中查找左右边界，可用于在排序数组中查找某个值出现的位置与次数等$n^2$

二.刷题沉淀

①花费最少爬楼梯

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # cost.append(0)
        # def min_cost(i):
        #     # 递归 -- 超时
        #     if i in (0,1):
        #         return cost[i]
            
        #     return cost[i] + min(min_cost(i-1),min_cost(i-2))
        
        # return min_cost(len(cost)-1)

        # # 带记忆的递归
        # cost.append(0)
        # cost_sum = [-1]*len(cost)
        # def min_cost(i):
        #     if i in (0,1): return cost[i]
        #     elif cost_sum[i] == -1:
        #         cost_sum[i] = cost[i] + min(min_cost(i-1),min_cost(i-2))
        #     return cost_sum[i]
        
        # return min_cost(len(cost)-1)
        
        # DP
        cost.append(0)
        i, n, cost_num = cost[0],cost[1],0
        for k in range(2,len(cost)):
            cost_num = min(i,n)+cost[k]
            i,n = n,cost_num
        
        return cost_num

②队列实现栈

# 双队列实现栈，等于把一个队列B存放之前的结果，把新的元素放入A后，再把B中之前的元素放入A
执行用时：32 ms, 在所有 Python3 提交中击败了94.87%的用户
内存消耗：15 MB, 在所有 Python3 提交中击败了35.37%的用户
from collections import deque
class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.A,self.B = deque(),deque()
        self.size = 0
    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.A.append(x)
        while self.B:
            self.A.append(self.B.popleft())
        self.A,self.B = self.B,self.A
        
        self.size += 1

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        self.size -= 1
        return self.B.popleft()

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.B[0]

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return self.size == 0

# 单队列实现栈，存储原有元素数量n，把新元素放入队列中后，执行n次pop-append操作，把之前的元素重新放入队列中
执行用时：40 ms, 在所有 Python3 提交中击败了61.83%的用户
内存消耗：14.8 MB, 在所有 Python3 提交中击败了93.24%的用户
from collections import deque
class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.A = deque()
        self.size = 0
    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.A.append(x)

        n = self.size
        while n > 0:
            self.A.append(self.A.popleft())
            n -= 1
        
        self.size += 1

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        self.size -= 1
        return self.A.popleft()

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.A[0]

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return self.size == 0