LeetCode 剑指Offer——顺时针打印矩阵、包含min函数的栈

顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

示例1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]

示例2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出：[1,2,3,4,8,12,11,10,9,5,6,7]

限制： 0 <= matrix.length <= 100 0 <= matrix[i].length <= 100

代码：

class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: if not matrix: return [] res, l, r, u, d = [], 0, len(matrix[0])-1, 0, len(matrix)-1 while True: for i in range(l, r+1): res.append(matrix[u][i]) u += 1 if u > d: break for i in range(u, d+1): res.append(matrix[i][r]) r -= 1 if l > r: break for i in range(r, l-1, -1): res.append(matrix[d][i]) d -= 1 if u > d: break for i in range(d, u-1, -1): res.append(matrix[i][l]) l += 1 if l > r: break return res

用模拟的方式从外到里顺时针访问矩阵。时间复杂度O(MN)，空间复杂度O(1)。

包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 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.

提示： 各函数的调用总次数不超过 20000 次

代码：

class MinStack: def __init__(self): self.A, self.B = [], [] def push(self, x: int) -> None: self.A.append(x) if not self.B or x <= self.B[-1]: self.B.append(x) def pop(self) -> None: if self.A.pop() == self.B[-1]: self.B.pop() def top(self) -> int: return self.A[-1] def min(self) -> int: return self.B[-1] # Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(x) # obj.pop() # param_3 = obj.top() # param_4 = obj.min()

这里利用辅助栈B实现，B中存放非严格降序的A栈元素。只要有不大于B栈顶的元素push进来则统统放入B栈，这保证了B栈顶必然存放最小元素，min函数时间复杂度为O(1)。同时pop操作时主栈A若pop出当前最小元素，B也应同步pop。

三个操作的时间复杂度都为O(1)，借助辅助栈空间复杂度为O(n)。