54. 螺旋矩阵
问题描述
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
解题思路
从外向内绕圈圈打印元素。
-
注意边界值的处理
官方题解图
代码实现
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int rowNum = matrix.length;
int colNum = matrix[0].length;
List<Integer> res = new ArrayList<>();
int left = 0, right = colNum - 1, top = 0, bottom = rowNum - 1;
while(left <= right && top <= bottom){
//打印上边界,包括两端端点
for(int i = left; i <= right; i++) {
res.add(matrix[top][i]);
}
//打印左边界，只包括下端点
for(int j = top + 1; j <= bottom; j++){
res.add(matrix[j][right]);
}
//处理单行或单列的情况
if(top == bottom || left == right){
break;
}
//打印下边界,不包括两端端点
for(int i = right - 1; i > left; i--) {
res.add(matrix[bottom][i]);
}
//打印右边界，只包括下端点
for(int j = bottom; j > top; j--){
res.add(matrix[j][left]);
}
left++;
right--;
top++;
bottom--;
}
return res;
}
}
155. 最小栈
问题描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
解题思路
引入辅助栈存储当前栈中的最小元素
代码实现
class MinStack {
private Deque<Integer> minElementStack;
private Deque<Integer> stack;
/** initialize your data structure here. */
public MinStack() {
stack = new LinkedList<>();
minElementStack = new LinkedList<>();
}
public void push(int x) {
if(stack.isEmpty() || x <= minElementStack.peek()){
//向辅助栈中添加元素
minElementStack.push(x);
}
stack.push(x);
}
public void pop() {
Integer top = stack.pop();
//如果弹出元素为当前栈中最小值，则辅助栈栈顶元素也弹出
if(top.equals(minElementStack.peek())){
minElementStack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minElementStack.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
946. 验证栈序列
问题描述
给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。
解题思路
使用一个辅助栈来模拟出栈，入栈操作。
代码实现
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Deque<Integer> stack = new LinkedList<>();
int popIndex = 0;
for(int i = 0 ; i < pushed.length; i++){
stack.push(pushed[i]);
while(popIndex < popped.length && !stack.isEmpty() && stack.peek().equals(popped[popIndex])){
//如果栈顶元素与出栈数组中的元素相同，则出栈
stack.pop();
popIndex++;
}
}
return stack.isEmpty();
}
}
