54. 螺旋矩陣
問題描述
給你一個 m 行 n 列的矩陣 matrix 桥嗤，請按照 順時針螺旋順序 展东，返回矩陣中的所有元素悄但。
解題思路
從外向內(nèi)繞圈圈打印元素锅棕。
-
注意邊界值的處理
官方題解圖
代碼實現(xiàn)
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. 最小棧
問題描述
設(shè)計一個支持 push ，pop 沐旨，top 操作森逮，并能在常數(shù)時間內(nèi)檢索到最小元素的棧。
push(x) —— 將元素 x 推入棧中磁携。
pop() —— 刪除棧頂?shù)脑亍?br>
top() —— 獲取棧頂元素。
getMin() —— 檢索棧中的最小元素良风。
解題思路
引入輔助棧存儲當(dāng)前棧中的最小元素
代碼實現(xiàn)
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();
//如果彈出元素為當(dāng)前棧中最小值谊迄，則輔助棧棧頂元素也彈出
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 兩個序列闷供，每個序列中的 值都不重復(fù)，只有當(dāng)它們可能是在最初空棧上進行的推入 push 和彈出 pop 操作序列的結(jié)果時统诺，返回 true歪脏；否則，返回 false 粮呢。
解題思路
使用一個輔助棧來模擬出棧婿失，入棧操作。
代碼實現(xiàn)
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])){
//如果棧頂元素與出棧數(shù)組中的元素相同啄寡，則出棧
stack.pop();
popIndex++;
}
}
return stack.isEmpty();
}
}
