《程序员代码面试指南》第一章 栈和队列
第一章 栈和队列
设计一个有getMIn功能的栈
题目：实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
要求：
1．pop、push、getMin 操作的时间复杂度都是 O(1)。
2．设计的栈类型可以使用现成的栈结构。
方法1：不同步压入：newValue <= getMin()才入最小值栈，代价是出栈操作更麻烦
public class Mystack1 {
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
public Mystack1() {
stackData = new Stack<>();
stackMin = new Stack<>();
}
// push:<=才入栈，说明是data和min是不同步压入
public void push(int newValue) {
if (stackMin.isEmpty()) {
stackMin.push(newValue);
} else if (newValue <= getMin()) {
stackMin.push(newValue);
}
stackData.push(newValue);
}
// pop：由于是不同步压入，data栈需要出找和getMin比较，相同两者都要出栈
public int pop() {
if (stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty");
}
int value = stackData.pop();
// 由于入栈是<=保证不同步压入，所以这里==就需要重新判断
if (value == getMin()) {
stackMin.pop();
}
return value;
}
public int getMin() {
if (stackMin.isEmpty()) {
throw new RuntimeException("Your stack is empty");
}
return stackMin.peek();
}
} 方法2：同步压入
public class Mystack2 {
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
public Mystack2() {
stackData = new Stack<>();
stackMin = new Stack<>();
}
// push：>=时候，data和min栈都同步压入，保证了其他方法的简单书写
public void push(int newValue) {
if (stackMin.isEmpty()) {
stackMin.push(newValue);
} else if (newValue < getStackMin()) {
stackMin.push(newValue);
} else {
stackMin.push(getStackMin());
}
stackData.push(newValue);
}
public int pop() {
if (stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty");
}
stackMin.pop();
return stackData.pop();
}
public int getStackMin() {
if (stackMin.isEmpty()) {
throw new RuntimeException("Your stack is empty");
}
return stackMin.peek();
}
} 力扣115：最小值栈
class MinStack {
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
public MinStack() {
stackData = new Stack<>();
stackMin = new Stack<>();
}
public void push(int x) {
if (stackMin.isEmpty()) {
stackMin.push(x);
} else if (x < getMin()) {
stackMin.push(x);
} else {
stackMin.push(getMin());
}
stackData.push(x);
}
public void pop() {
if (stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty");
}
stackMin.pop();
stackData.pop();
}
public int top() {
if (stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty");
}
return stackData.peek();
}
public int getMin() {
if (stackMin.isEmpty()) {
throw new RuntimeException("Your stack is empty");
}
return stackMin.peek();
}
} 由两个栈组成的队列
题目：编写一个类，用两个栈实现队列，支持队列的基本操作（add、poll、peek）。
问题：利用两个栈，定义一个pushToPop方法简化操作
1．如果 stackPush 要往 stackPop 中压入数据，那么必须一次性把 stackPush 中的数据全部压入。
- 1
5 依次压入 stackPush，stackPush 的栈顶到栈底为 51，从 stackPush压入 stackPop 时，只将 5 和 4 压入了 stackPop，stackPush 还剩下 1、2、3 没有压入。此时如果用户想进行弹出操作，那么 4 将最先弹出，与预想的队列顺序就不一致。
2．如果 stackPop 不为空，stackPush 绝对不能向 stackPop 中压入数据。违反了以上两点都会发生错误。
- 违反 2 的情况举例：1
5 依次压入 stackPush，stackPush 将所有的数据压入 stackPop，此时从 stackPop 的栈顶到栈底就变成了 15。此时又有 6~10 依次压入 stackPush，stackPop 不为空，stackPush 不能向其中压入数据。如果违反 2 压入了 stackPop，从 stackPop 的栈顶到栈底就变成了 6-10、1-5。那么此时如果用户想进行弹出操作，6 将最先弹出，与预想的队列顺序就不一致。
public class TwoStacksQueue {
private Stack<Integer> stackPush;
private Stack<Integer> stackPop;
public TwoStacksQueue() {
stackPush = new Stack<Integer>();
stackPop = new Stack<Integer>();
}
// 定义一个压栈函数:如果pop栈为空，就一次性把push栈中元数入pop栈
private void pushToPop() {
if (stackPop.empty()) {
while (!stackPush.empty()) {
stackPop.push(stackPush.pop());
}
}
}
// 添加之后，保证一个压栈操作
public void add(int pushInt) {
stackPush.push(pushInt);
pushToPop();
}
// 出栈之前，保证一个压栈操作
public int poll() {
if (stackPush.empty() && stackPop.empty()) {
throw new RuntimeException("Queue is empty");
}
pushToPop();
return stackPop.pop();
}
// 出栈之前，保证一个压栈操作
public int peek() {
if (stackPush.empty() && stackPop.empty()) {
throw new RuntimeException("Queue is empty");
}
pushToPop();
return stackPop.peek();
}
// 判空之前，保证一个压栈操作
public boolean empty() {
pushToPop();
return stackPush.isEmpty();
}
} 力扣232：用栈实现队列
方法：使用左神的pushToPop（）方法，摊还时间复杂度
class MyQueue {
private Stack<Integer> stackPush;
private Stack<Integer> stackPop;
public MyQueue() {
stackPush = new Stack<Integer>();
stackPop = new Stack<Integer>();
}
private void pushToPop() {
while (stackPop.isEmpty()) {
while (!stackPush.isEmpty()) {
stackPop.push(stackPush.pop());
}
}
}
public void push(int x) {
stackPush.push(x);
pushToPop();
}
public int pop() {
if (empty()) {
throw new IllegalArgumentException("Stack is Empty");
}
pushToPop();
return stackPop.pop();
}
public int peek() {
if (empty()) {
throw new IllegalArgumentException("Stack is Empty");
}
pushToPop();
return stackPop.peek();
}
public boolean empty() {
return stackPush.isEmpty() && stackPop.isEmpty();
}
} 力扣225：用队列实现栈
方法1：使用一个队列，为了实现后进先出，先记录原数组的个数n，进栈后原个数的元素出栈再进栈
class MyStack {
Queue<Integer> q;
public MyStack() {
q = new LinkedList<>();
}
// push:先记录之前队列个数，元素入队列后，再出之前队中元素入队
public void push(int x) {
int n = q.size();
q.offer(x);
for (int i = 0; i < n; i++) {
q.offer(q.poll());
}
}
public int pop() {
return q.poll();
}
public int top() {
return q.peek();
}
public boolean empty() {
return q.isEmpty();
}
} 方法2：使用2个队列，q1始终指向数据队列，q2是辅助队列。q2先入元素，再将q1的元素倒入q2，最后交换2个队列，
class MyStack1 {
LinkedList<Integer> queue1;
LinkedList<Integer> queue2;
public MyStack1() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
public void push(int x) {
// 1.q2先入元素，辅助队列中暂存队列头的元素
queue2.offer(x);
// 2.q1中的元素全部入q2
while (!queue1.isEmpty()) {
queue2.offer(queue1.poll());
}
// 3.交换2个栈
LinkedList<Integer> temp;
temp = queue1;
queue1 = queue2;
queue2 = temp;
}
public int pop() {
return queue1.poll();
}
public int top() {
return queue1.peek();
}
public boolean empty() {
return queue1.isEmpty();
}
} 递归逆序一个栈
题目：一个栈依次压入 1、2、3、4、5，那么从栈顶到栈底分别为 5、4、3、2、1。将这个栈转置后，从栈顶到栈底为 1、2、3、4、5，也就是实现栈中元素的逆序，但是只能用递归函数来实现，不能用其他数据结构。
方法：实现一个获取栈底元素其他元素不变的函数+主函数逆序
public class Reverse {
public static void reverse(Stack<Integer> stack) {
// 1.递归结束:因为get操作有弹出，肯定是栈空为结束
if (stack.isEmpty()) {
return;
}
// 2.想成普通方法，一次获得栈底元素
int i = getAndRemoveLastElement(stack);
// 3.递归逆序入栈
reverse(stack);
stack.push(i);
}
// 返回栈底元素
private static int getAndRemoveLastElement(Stack<Integer> stack) {
// 1.先弹出栈顶元素
int result = stack.pop();
// 2.递归结束：栈为空，返回当前弹出元素
if (stack.empty()) {
return result;
} else {
// 3.这里递归得到last = 栈底元素
int last = getAndRemoveLastElement(stack);
// 4.每一次都原栈的元素返回去
stack.push(result);
// 5.每一次递归返回都是最后一个元素
return last;
}
}
} 猫狗队列
题目：猫狗队列如下，请实现一个数据结构，add、pollAll、pollDog、pollCat等方法。要求是能按照进入队列的顺序依次出队
public class DogCatQueue {
public DogCatQueue() {
}
public void add(Pet pet) {
}
public Pet pollAll() {
}
public Dog pollDog() {
}
public Cat pollCat() {
}
public boolean isEmpty() {
}
public boolean isDogQueueEmpty() {
}
public boolean isCatQueueEmpty() {
}
} 条件类：
public class Pet {
private String type;
public Pet(String type) {
this.type = type;
}
public String getPetType() {
return this.type;
}
} public class Cat extends Pet {
public Cat() {
super("cat");
}
} public class Dog extends Pet {
public Dog() {
super("dog");
}
} 方法：实现一个PetEnterQueue类，盖上时间戳。
public class PetEnterQueue {
private Pet pet;
private long count;
public PetEnterQueue(Pet pet, long count) {
this.pet = pet;
this.count = count;
}
public Pet getPet(){
return this.pet;
}
public long getCount() {
return this.count;
}
public String getEnterPetType(){
return this.pet.getPetType();
}
} public class DogCatQueue {
private Queue<PetEnterQueue> dogQ;
private Queue<PetEnterQueue> catQ;
// 时间戳
private long count;
public DogCatQueue() {
this.dogQ = new LinkedList<PetEnterQueue>();
this.catQ = new LinkedList<PetEnterQueue>();
this.count = 0;
}
public void add(Pet pet) {
if (pet.getPetType().equals("dag")) {
dogQ.add(new PetEnterQueue(pet, count++));
} else if (pet.getPetType().equals("cat")) {
catQ.add(new PetEnterQueue(pet, count++));
} else {
throw new RuntimeException("err,not dog or cat");
}
}
public Pet pollAll() {
if (!dogQ.isEmpty() && !catQ.isEmpty()) {
if (dogQ.peek().getCount() < catQ.peek().getCount()) {
return dogQ.poll().getPet();
} else {
return catQ.poll().getPet();
}
} else if (!dogQ.isEmpty()) {
return dogQ.poll().getPet();
} else if (!catQ.isEmpty()) {
return catQ.poll().getPet();
} else {
throw new RuntimeException("err,queue is empty");
}
}
public Dog pollDog() {
if (!isDogQueueEmpty()) {
return (Dog) dogQ.poll().getPet();
} else {
throw new RuntimeException("DogQueue is empty");
}
}
public Cat pollCat() {
if (!isCatQueueEmpty()) {
return (Cat) catQ.poll().getPet();
} else {
throw new RuntimeException("CatQueue is empty");
}
}
public boolean isEmpty() {
return dogQ.isEmpty() && catQ.isEmpty();
}
public boolean isDogQueueEmpty() {
return dogQ.isEmpty();
}
public boolean isCatQueueEmpty() {
return catQ.isEmpty();
}
} 用一个栈实现另一个栈的排序
题目：一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？
方法：使用一个辅助栈，保存从小到大的排序
public static void sortStackByStack(Stack<Integer> stack) {
// 1.使用一个辅助栈，将stack栈中从小到大排序
Stack<Integer> help = new Stack<>();
while (!stack.isEmpty()) {
int cur = stack.pop();
// 2.反过来想，cur>辅助栈顶，辅助栈出栈进原栈
while (!help.isEmpty() && cur > help.peek()) {
stack.push(help.pop());
}
// 3.cur<=辅助栈顶，就入辅助栈
help.push(cur);
}
// 4.遍历辅助栈元素，依次进原栈，实现原栈栈顶到栈底从大到小
while (!help.isEmpty()) {
stack.push(help.pop());
}
} 用栈来求解汉诺塔问题
回顾原汉诺塔问题：假设有 from 柱子、mid 柱子和 to 柱子，都从 from 的圆盘 1~i 完全移动到 to，最优过程为：
步骤 1：为圆盘 1~n-1 从 from 移动到 mid。
步骤 2：为单独把圆盘 n 从 from 移动到 to。
步骤 3：为把圆盘 1~n-1 从 mid 移动到 to。如果圆盘只有 1 个，直接把这个圆盘从 from 移动到 to 即可。
public static void hanoi(int n) {
if (n > 0) {
hanoi(n, "left", "mid", "right");
}
}
private static void hanoi(int n, String from, String mid, String to) {
if (n == 1) {
System.out.println("Move from " + from + " to " + to);
} else {
hanoi(n - 1, from, to, mid);
hanoi(1, from, mid, to);
hanoi(n - 1, mid, from, to);
}
} 力扣面试题 08.06. 汉诺塔问题：
class Solution {
public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
if (A.size() > 0) {
hanota(A.size(), A, B, C);
}
}
private void hanota(int n, List<Integer> A, List<Integer> B, List<Integer> C) {
// 递归结束条件:n=0就结束
if (n < 1) {
return;
}
hanota(n - 1, A, C, B);
C.add(A.remove(A.size() - 1));
hanota(n - 1, B, A, C);
}
} 题目：汉诺塔问题比较经典，这里修改一下游戏规则：现在限制不能从最左侧的塔直接移动到最右侧，也不能从最右侧直接移动到最左侧，而是必须经过中间。求当塔有 N 层的时候，打印最优移动过程和最优移动总步数。
例如，当塔数为两层时，最上层的塔记为 1，最下层的塔记为 2，则打印：
Move 1 from left to mid Move 1 from mid to right Move 2 from left to mid Move 1 from right to mid Move 1 from mid to left Move 2 from mid to right Move 1 from left to mid Move 1 from mid to right It will move 8 steps.
递归法：
public class HanoiProblem1 {
// 递归法
public static int hanoiProblem1(int num, String left, String mid, String right) {
if (num < 1) {
return -1;
}
// 定义process函数，添加from、to函数
return process(num, left, mid, right, left, right);
}
public static int process(int num, String left, String mid, String right, String from, String to) {
// 1.递归结束条件
if (num == 1) {
if (from.equals("mid") || to.equals("mid")) {
System.out.println("Move 1 from " + from + " to " + to);
return 1;
} else {
System.out.println("Move 1 from " + from + " to " + mid);
System.out.println("Move 1 from " + mid + " to " + to);
return 2;
}
}
// 2.左到中||中到左||右到中||中到右
if (from.equals("mid") || to.equals("mid")) {
String another = (from.equals("left") | to.equals("left")) ? right : left;
int part1 = process(num - 1, left, mid, right, from, another);
int part2 = 1;
System.out.println("Move " + num + " from " + from + " to " + to);
int part3 = process(num - 1, left, mid, right, another, to);
return part1 + part2 + part3;
} else {
int part1 = process(num - 1, left, mid, to, from, to);
int part2 = 1;
System.out.println("Move " + num + " from " + from + " to " + mid);
int part3 = process(num - 1, left, mid, right, to, from);
int part4 = 1;
System.out.println("Move " + num + " from " + mid + " to " + to);
int part5 = process(num - 1, left, mid, to, from, to);
return part1 + part2 + part3 + part4 + part5;
}
}
} 非递归法：
public class HanoiProblem2 {
public static int hanoiProblem2(int num, String left, String mid, String right) {
Stack<Integer> ls = new Stack<>();
Stack<Integer> ms = new Stack<>();
Stack<Integer> rs = new Stack<>();
// 3个栈都加入最大值， 保证fStack.peek() < tStack.peek()不发生异常
ls.push(Integer.MAX_VALUE);
ms.push(Integer.MAX_VALUE);
rs.push(Integer.MAX_VALUE);
for (int i = num; i > 0; i--) {
ls.push(i);
}
Action[] record = {Action.No};
int step = 0;
while (rs.size() <=num) {
step += fStackToStack(record, Action.MToL, Action.LToM, ls, ms, left, mid);
step += fStackToStack(record, Action.LToM, Action.MToL, ms, ls, mid, left);
step += fStackToStack(record, Action.RToM, Action.MToR, ms, rs, mid, right);
step += fStackToStack(record, Action.MToR, Action.RToM, rs, ms, right, mid);
}
return step;
}
// 定义行为函数
public enum Action {
No, LToM, MToL, MToR, RToM
}
// 出入栈函数
public static int fStackToStack(Action[] record, Action preNoAct, Action nowAct,
Stack<Integer> fStack, Stack<Integer> tStack,
String from, String to) {
// 不相邻原则 && 小压大原则
if (record[0] != preNoAct && fStack.peek() < tStack.peek()) {
// 满足条件就入栈，打印
tStack.push(fStack.pop());
System.out.println("Move " + tStack.peek() + " from " + from + " to " + to);
// 更改行为
record[0] = nowAct;
return 1;
}
return 0;
}
public static void main(String[] args) {
int step = hanoiProblem2(2, "left", "mid", "right");
System.out.println("It will move " + step + " steps");
}
} 滑动窗口最大值数组
题目：有一个整型数组 arr 和一个大小为 w 的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。
方法：使用双端队列qmax，标记最大值数组，长度为n-w+1
- arr[qMax.peekLast()] > arr[i]入队列
- arr[qMax.peekLast()] <= arr[i]末尾出队列
- qMax.peekFirst() == i - w时，滑动窗口开头索引后移一位，qMax队头出队列
- i >= w - 1时，就要将队头元数入结果集
public static int[] getMaxWindow(int[] arr, int w) {
if (arr == null || w < 1 || arr.length < w) {
return null;
}
// qMax保存最大值下标
LinkedList<Integer> qMax = new LinkedList<>();
// res长度：n-w+1个窗口最大值
int[] res = new int[arr.length - w + 1];
int index = 0;
for (int i = 0; i < arr.length; i++) {
// 队中索引的值<=数组的值，就出队尾元素
while (!qMax.isEmpty() && arr[qMax.peekLast()] <= arr[i]) {
qMax.pollLast();
}
// 队中索引的值>数组的值,就入队尾
qMax.addLast(i);
// 移动qMax窗口:从i-w开始，队头就得出一个
if (qMax.peekFirst() == i - w) {
qMax.pollFirst();
}
// 从w-1索引开始，最大值需要加入结果集res中
if (i >= w - 1) {
res[index++] = arr[qMax.peekFirst()];
}
}
return res;
} 力扣239：同一题，改下参数名即可
class Solution {
// 剑指 Offer 59 - I. 滑动窗口的最大值
// 239. 滑动窗口最大值
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length < k || nums.length < 1 || k < 1) {
return new int[]{};
}
LinkedList<Integer> q = new LinkedList<Integer>();
int[] res = new int[nums.length - k + 1];
int index = 0;
for (int i = 0; i < nums.length; i++) {
while (!q.isEmpty() && nums[q.peekLast()] <= nums[i]) {
q.pollLast();
}
q.addLast(i);
if (q.peekFirst() == i - k) {
q.pollFirst();
}
if (i >= k - 1) {
res[index++] = nums[q.peekFirst()];
}
}
return res;
}
} 单调栈
原题目：给定一个不含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i]小的位置。返回所有位置相应的信息。
arr = {3,4,1,5,6,2,7}
返回如下二维数组作为结果：
{
{-1, 2},
{ 0, 2},
{-1,-1},
{ 2, 5},
{ 3, 5},
{ 2,-1},
{ 5,-1}
} 方法：原数组无重复元素，使用一个栈，存放数组索引，栈顶元素为j，带入栈的元素是i（=i是遍历数组的指针）
- arr[stack[j]]<arr[i]就入栈
- arr[stack[j]]>=arr[i]就出栈顶元素，直到满足1的条件停止再入栈
- 怎么记？保证栈中元素从栈顶到栈底的指针在原数组中的值是严格递减的，自己想象一个栈画面即可
// 给定一个不重复的数组，找到左右最靠近小于它的下标
public static int[][] getNearLessNoRepeat(int[] arr) {
Stack<Integer> stack = new Stack<>();
int[][] res = new int[arr.length][2];
for (int i = 0; i < arr.length; i++) {
// 遍历辅助栈，peek()>arr[i]就要出栈
while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
int popIndex = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
res[popIndex][0] = leftLessIndex;
res[popIndex][1] = i;
}
stack.push(i);
}
while (!stack.isEmpty()) {
int popIndex = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
res[popIndex][0] = leftLessIndex;
// 遍历辅助栈时，因为无数再入，所以值为-1
res[popIndex][1] = -1;
}
return res;
} 进阶问题：如果原数组含有重复数组，怎么办？
方法：整体方法与上面一致，只是栈中存储链表，相同元素的就用链表依次链接下去，出栈的时候出链表末尾
// 给定一个重复的数组，找到左右最靠近小于它的下标
public static int[][] getNearLessNoRepeat(int[] arr) {
int[][] res = new int[arr.length][2];
Stack<List<Integer>> stack = new Stack<>();
for (int i = 0; i < arr.length; i++) {
// 大于
while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
List<Integer> popList = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
for (Integer popValue : popList) {
res[popValue][0] = leftLessIndex;
res[popValue][1] = i;
}
}
// 等于
if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
stack.peek().add(i);
} else {// 小于
LinkedList<Integer> list = new LinkedList<>();
list.add(i);
stack.push(list);
}
}
// 栈不空，就遍历出栈
while (!stack.isEmpty()) {
List<Integer> popList = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.size() - 1);
for (Integer popValue : popList) {
res[popValue][0] = leftLessIndex;
res[popValue][1] = -1;
}
}
return res;
} 求最大子矩阵的面积
题目：给定一个整型矩阵 map，其中的值只有 0 和 1 两种，求其中全是 1 的所有矩形区域中，最大的矩形区域为 1 的数量。
1 0 1 1 1 1 1 1 1 1 1 0 其中，最大的矩形区域有 6 个 1，所以返回 6。
方法：使用一个height数组保存数组每一行的1个数；使用一个单调栈保存索引，遍历指针i，栈顶元素j，弹出后的栈顶元素k
- height[j]<height[i]入栈
- height[j]>=height[i]就出栈顶元素，直到满足1的条件停止再入栈
- 由于是栈顶到栈底单调栈性质，所以j左边能构成最大面积起始位置是k+1，右边能构成最大面试终点位置是i-1，整体面积大小是[i-1-(k+1)]*height[j]
public static int maxRecSize(int[][] map) {
if (map == null || map.length == 0 || map[0].length == 0) {
return 0;
}
int maxArea = 0;
int[] height = new int[map[0].length];
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
height[j] = map[i][j] == 0 ? 0 : height[j] + 1;
}
maxArea = Math.max(maxRecFromBottom(height), maxArea);
}
return maxArea;
}
public static int maxRecFromBottom(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int maxArea = 0;
Stack<Integer> stack = new Stack<>();
// 遍历h数组，使用单调栈判断业务逻辑
for (int i = 0; i < height.length; i++) {
// 1.单调栈，先写出栈的逻辑：h[i]<=h[j]就不断出栈
while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {
int j = stack.pop();
int k = stack.isEmpty() ? -1 : stack.peek();
int curArea = (i - k - 1) * height[j];
maxArea = Math.max(curArea, maxArea);
}
stack.push(i);
}
// 遍历完h数组后，如果栈中还有元素，就出栈
while (!stack.isEmpty()) {
int j = stack.pop();
int k = stack.isEmpty() ? -1 : stack.peek();
int curArea = (height.length - k - 1) * height[j];
maxArea = Math.max(curArea, maxArea);
}
return maxArea;
} 力扣85：最大数组。参数是字符数组，转化成整型数组就行，其余问题一样
public class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int[][] map = new int[matrix.length][matrix[0].length];
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
map[i][j] = Integer.parseInt(String.valueOf(matrix[i][j]));
}
}
int maxArea = 0;
int[] height = new int[map[0].length];
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
height[j] = map[i][j] == 0 ? 0 : height[j] + 1;
}
maxArea = Math.max(maxRecFromBottom(height), maxArea);
}
return maxArea;
}
public int maxRecFromBottom(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int maxArea = 0;
Stack<Integer> stack = new Stack<>();
// 遍历h数组，使用单调栈判断业务逻辑
for (int i = 0; i < height.length; i++) {
// 1.单调栈，先写出栈的逻辑：h[i]<=h[j]就不断出栈
while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {
int j = stack.pop();
int k = stack.isEmpty() ? -1 : stack.peek();
int curArea = (i - k - 1) * height[j];
maxArea = Math.max(curArea, maxArea);
}
stack.push(i);
}
// 遍历完h数组后，如果栈中还有元素，就出栈
while (!stack.isEmpty()) {
int j = stack.pop();
int k = stack.isEmpty() ? -1 : stack.peek();
int curArea = (height.length - k - 1) * height[j];
maxArea = Math.max(curArea, maxArea);
}
return maxArea;
}
} 最大值减去最小值<=num的子数组数量
题目：给定数组 arr 和整数 num，共返回有多少个子数组满足如下情况：
max(arr[i..j]) - min(arr[i..j]) <= num max(arr[i..j])表示子数组 arr[i..j]中的最大值，min(arr[i..j])表示子数组 arr[i..j]中的最小值。
方法：
生成两个双端队列 qmax 和 qmin，含义如上文所说。生成两个整型变量 i 和 j，表示子数组的范围，即 arr[i..j]。生成整型变量 res，表示所有满足条件的子数组数量。
令 j 不断向右移动（j++），表示 arr[i..j]一直向右扩大，并不断更新 qmax 和 qmin 结构，保证 qmax 和 qmin 始终维持动态窗口最大值和最小值的更新结构。一旦出现 arr[i..j]不满足条件的情况，j 向右扩的过程停止，此时 arr[i..j-1]、arr[i..j-2]、arr[i..j-3]...arr[i..i]一定都是满足条件的。也就是说，所有必须以 arr[i]作为第一个元素的子数组，满足条件的数量为 j-i 个。于是令 res+=j-i。
当进行完步骤 2，令 i 向右移动一个位置，并对 qmax 和 qmin 做出相应的更新，qmax和 qmin 从原来的 arr[i..j]窗口变成 arr[i+1..j]窗口的最大值和最小值的更新结构。然后重复步骤 2，也就是求所有必须以 arr[i+1]作为第一个元素的子数组中，满足条件的数量有多少个。
根据步骤 2 和步骤 3，依次求出：必须以 arr[0]开头的子数组，满足条件的数量有多少个；必须以 arr[1]开头的子数组，满足条件的数量有多少个；必须以 arr[2]开头的子数组，满足条件的数量有多少个，全部累加起来就是答案。上述过程中，所有的下标值最多进 qmax 和 qmin 一次，出 qmax 和 qmin 一次。i 和 j 的值也不断增加，并且从来不减小。所以整个过程的时间复杂度为 O(N)。
public int getNum(int[] arr, int num) {
if (arr == null || arr.length == 0 || num < 0) {
return 0;
}
LinkedList<Integer> qMax = new LinkedList<>();
LinkedList<Integer> qMin = new LinkedList<>();
int i = 0, j = 0;
int res = 0;
while (i < arr.length) {
while (j < arr.length) {
if (qMin.isEmpty() || qMin.peekLast() != j) {
while (!qMin.isEmpty() && arr[qMin.peekLast()] >= arr[j]) {
qMin.pollLast();
}
qMin.add(j);
while (!qMax.isEmpty() && arr[qMax.peekLast()] <= arr[j]) {
qMax.pollLast();
}
qMax.add(j);
}
if (qMax.peekFirst() - qMin.peekFirst() > num) {
break;
}
j++;
}
// j++以后跳出循环，所以不用+1,直接j-i就行
res += j - i;
if (qMin.peekFirst() == i) {
qMin.pollFirst();
}
if (qMax.peekFirst() == i) {
qMax.pollFirst();
}
i++;
}
return res;
} 可见的山峰数量
原题目:给定一个不含有负数且没有重复值的数组 arr，请返回有多少对山峰能够相互看见。
答案:数学推导，假设环形结构中有i座山峰（i>2),可见山峰数为2*i-3
进阶问题：给定一个不含有负数但可能含有重复值的数组 arr，返回有多少对山峰能够相互看见。
方法：
- 定义一个Reord类，保存数组值和该元素出现的次数/山峰数
- 遍历arr，得出最大值索引，Record（arr[maxIndex],1）放进一个栈里
- 定义nextIndex方法获取maxIndex的逆时针索引。逆时针遍历arr
- stack.peek().value < arr[index]，弹出栈，计算山峰数:栈顶*2+C(2,次数)
- stack.peek().value == arr[index]，栈顶元素次数加1
- stack.peek().value > arr[index]，正常入栈
- 栈非空，就清算栈里元素,k为栈顶元素次数
- stack.size() > 2 ，循环操作。res+=2*k+C(2,k)
- stack.size() == 2，只有一次操作。k=1,res+=k；k>1,res+=k*2+C(2,k)
- stack.size() > 2，必然存在的操作，因为栈底是最大值。k=1,res+=0;k>1,res+=C(2,k)
public static int getVisibleNum(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int size = arr.length;
int maxIndex = 0;
// 现在环中找到一个最大值，哪个索引都行
for (int i = 0; i < size; i++) {
maxIndex = arr[maxIndex] < arr[i] ? i : maxIndex;
}
// 单调栈：要求从栈底到栈顶严格递减
Stack<Record> stack = new Stack<>();
// 将(最大值,1)放入栈底
stack.push(new Record(arr[maxIndex]));
// 从最大值的逆时针开始遍历
int index = nextIndex(maxIndex, size);
int res = 0;
while (index != maxIndex) {
// >就出栈
while (stack.peek().value < arr[index]) {
int k = stack.pop().times;
res += 2 * k + getInternalSum(k);
}
// =就次数加1
if (stack.peek().value == arr[index]) {
stack.peek().times++;
} else {
// >就入栈
stack.push(new Record(arr[index]));
}
index = nextIndex(index, size);
}
// 清算第1阶段：弹出的记录不是栈中倒数2个位置
while (stack.size() > 2) {
int k = stack.pop().times;
res += 2 * k + getInternalSum(k);
}
// 清算第2阶段：弹出的记录是倒数1个位置
while (stack.size() == 2) {
int k = stack.pop().times;
// 以下的stack.peek().times就是栈底元素了
res += (stack.peek().times == 1 ? k : k * 2) + getInternalSum(k);
}
// 清算第3阶段：弹出的记录是栈底
res += getInternalSum(stack.peek().times);
return res;
}
public static int getInternalSum(int k) {
// k>1:C(2,k)= (k * (k - 1) / 2)
return k == 1 ? 0 : (k * (k - 1) / 2);
}
// 环形数组中当前位置为i，返回i的下一个索引
private static int nextIndex(int i, int size) {
return i < (size - 1) ? i + 1 : 0;
}
补充题
力扣20：有效的括号。
题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
输入: "(]" 输出: false
方法：
- 使用一个栈，遍历字符串，遇到左边括号就入栈
- 否则栈非空，就出栈一个元素，如果不匹配当前遍历字符，返回false;栈空，也返回false
public class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.isEmpty()) {
return false;
}
Character pop = stack.pop();
if (c == ')' && pop != '(') {
return false;
}
if (c == '}' && pop != '{') {
return false;
}
if (c == ']' && pop != '[') {
return false;
}
}
}
return stack.isEmpty();
}
} 力扣71：简化路径
题目：以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。
输入："/home/" 输出："/home" 解释：注意，最后一个目录名后面没有斜杠。 输入："/../" 输出："/" 解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。 输入："/home//foo/" 输出："/home/foo" 解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。 输入："/a/../../b/../c//.//" 输出："/c" 输入："/a//b////c/d//././/.." 输出："/a/b/c"
public class Solution {
public String simplifyPath(String path) {
// 1.spilt分字符,然后遍历字符数组
String[] splits = path.split("/");
Stack<String> stack = new Stack<>();
for (String s : splits) {
// 2.trim分割当前元素的前后空格
String cur = s.trim();
// 3.如果当前字符为空||为.，跳出当前循环
if (cur == null || cur.length() == 0 || cur.equals(".")) {
continue;
}
// 4.当前元素是..，非空栈就得出栈元素
if (cur.equals("..")) {
if (!stack.isEmpty()) {
stack.pop();
}
} else { // 5.遍历到其他元素就入栈
stack.push(cur);
}
}
// 6.出栈，构成结果
StringBuilder res = new StringBuilder();
while (!stack.isEmpty()) {
res.insert(0, "/" + stack.pop());
}
// 7 res为空，返回”/“,否则返回res.toString
return res.length() == 0 ? "/" : res.toString();
}
} 
长安汽车成长空间 27人发布