OptimalSolution(6)--栈和队列
一、设计一个有getMin功能的栈
题目：实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。pop、push、getMin操作的时间复杂度都是O(1).
思路：设计两个栈，一个栈用来保存当前栈中的元素，其功能和一个正常的栈没有区别，这个栈记为stackData；另一个栈用来保存每一步的最小值，记为stackMin
解法1：
push：假设当前数据为newNum，先将其压入stackData。然后判断stackMin是否为空：（1）如果为空，则newNum也压入栈（2）如果不为空，比较newNum和stackMin的栈顶元素哪一个更小。如果newNum更小或两者相等，则newNum也压入栈stackMin；如果stackMin栈顶元素小，则stackMin不压入。
例如，给定3,4,5,1,2,1，操作完成后，stackData：3 4 5 1 2 1（栈顶），stackMin：3 无 无 1 无 1
pop：先在stackData中弹出，记为value，然后比较当前stackMin栈顶元素和value，value只可能大于或等于stackMin栈顶元素。如果value等于stackMin栈顶元素，stackMin弹出栈顶元素；如果value大于stackMin栈顶元素，stackMin不弹出栈顶元素；返回value
getMin：stackMin的栈顶元素始终是stackData中的最小值。
package Chapter1;
import java.util.Stack;
public class MyStack1 {
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
public MyStack1() {
this.stackData = new Stack<>();
this.stackMin = new Stack<>();
}
public void push(int newNum) {
if (stackMin.isEmpty()) {
stackMin.push(newNum);
} else if (newNum <= stackMin.peek()) {
stackMin.push(newNum);
}
stackData.push(newNum);
}
public int pop() {
if (stackData.isEmpty()) {
throw new RuntimeException("stack is empty, cannot pop");
}
int value = stackData.pop();
if (value == stackMin.peek()) {
stackMin.pop();
}
return value;
}
public int getMin() {
if (stackMin.isEmpty()) {
throw new RuntimeException("stack is empty, cannot getMin");
}
return stackMin.peek();
}
}
带有getMin功能的栈，实现1
解法2：
push：假设当前数据为newNum，先将其压入stackData。然后判断stackMIn是否为空，如果为空，newNum也压入stackMin；如果不为空，比较newNum和stackMin栈顶元素：（1）如果newNum更小或者相等，则newNum也压入stackMin中；如果stackMin栈顶元素小，则把stackMin的栈顶元素重复压入stackMin。
例如：给定3,4,5,1,2,1，操作完成后，stackData：3 4 5 1 2 1（栈顶），stackMin：3 3 3 1 1 1
pop：弹出stackData栈顶元素，同时弹出stackMin栈顶元素
getMin：stackMin栈顶元素即为最小值
package Chapter1;
import java.util.Stack;
public class MyStack2 {
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
public MyStack2() {
this.stackData = new Stack<>();
this.stackMin = new Stack<>();
}
public void push(int newNum) {
if (stackMin.isEmpty()) {
stackMin.push(newNum);
} else if (newNum < stackMin.peek()) {
stackMin.push(newNum);
} else {
int newMin = stackMin.peek();
stackMin.push(newMin);
}
stackData.push(newNum);
}
public int pop() {
if (stackData.isEmpty()) {
throw new RuntimeException("stack is empty, cannot pop");
}
stackMin.pop();
return stackData.pop();
}
public int getMin() {
if (stackMin.isEmpty()) {
throw new RuntimeException("stack is empty, cannot getMin");
}
return stackMin.peek();
}
}
带有getMin功能的栈，实现2
二、用一个栈实现另一个栈的排序
题目：想让栈从顶到底按从大到小的顺序排序，只许申请一个栈，可以申请新的变量，不能申请新的数据结构。
解法：要排序的栈记为stack，申请的辅助栈记为help。在stack上执行pop操作时，弹出的元素记为cur：（1）如果cur小于或等于help的栈顶元素，则将cur直接压入help（2）如果cur大于help的栈顶元素，则将help的元素逐一弹出，并逐一压入stack，直到cur小于或等于help的栈顶元素，再将cur压入help。最后将help中所有元素依次压入stack即可。
public static void sortStackByStack(Stack<Integer> stack) {
Stack<Integer> help = new Stack<>();
while (!stack.isEmpty()) {
int cur = stack.pop();
while (!help.isEmpty() && help.peek() > cur) {
stack.push(help.pop());
}
help.push(cur);
}
while (!help.isEmpty()) {
stack.push(help.peek());
}
}
用一个栈实现另一个栈的排序
三、由两个栈组成的队列
题目：用两个栈实现队列，支持队列的基本操作（add、poll、peek）。
解法：使用两个栈，一个作为压入栈，一个作为弹出栈。必须注意两点，如果stackPush要往stackPop中压入数据，则必须一次性把stackPush中的数据全部压入；如果stackPop不为空，stackPush绝对不能向stackPop中压入数据。
package Chapter1;
import java.util.Stack;
public class MyQueue {
public Stack<Integer> stackPush;
public Stack<Integer> stackPop;
public MyQueue() {
stackPush = new Stack<>();
stackPop = new Stack<>();
}
public void add(int newNum) {
stackPush.push(newNum);
}
public int poll() {
if (stackPush.isEmpty() && stackPop.isEmpty()) {
throw new RuntimeException("The Queue is Empty, cannot poll");
} else if (stackPop.isEmpty()) {
while (!stackPush.isEmpty()) {
stackPop.push(stackPush.pop());
}
}
return stackPop.pop();
}
public int peek() {
if (stackPush.isEmpty() && stackPop.isEmpty()) {
throw new RuntimeException("The Queue is Empty, cannot poll");
} else if (stackPop.isEmpty()) {
while (!stackPush.isEmpty()) {
stackPop.push(stackPush.pop());
}
}
return stackPop.peek();
}
}
用两个栈组成队列
四、仅用递归函数和栈操作逆序一个栈
问题：一个栈依次压入1,2,3,4,5，那么从栈顶到栈底分别为5,4,3,2,1，将这个栈逆序后，从栈顶到栈底1,2,3,4,5，只能使用递归函数实现栈的逆序。
递归函数1：将栈stack的栈底元素返回并移除
例如，stack的栈顶到栈底依次为3,2,1，则过程是弹出3，弹出2，弹出1，压入2，压入3，返回1。
public static int getAndRemoveLastElement(Stack<Integer> stack) {
int result = stack.pop();
if (stack.isEmpty()) {
return result;
} else {
int last = getAndRemoveLastElement(stack);
stack.push(result);
return last;
}
}
递归函数2：逆序一个栈，使用到了getAndRemoveLastElement方法。
例如，stack的栈顶到栈底依次为3,2,1，则过程是弹出1，弹出2，弹出3，栈空，压入3，压入2，压入1，结束
public static void reverse(Stack<Integer> stack) {
if (stack.isEmpty()) {
return;
}
int i = getAndRemoveLastElement(stack);
reverse(stack);
stack.push(i);
}
五、猫狗队列
题目：猫狗队列的要求是：
- 调用add方法将cat类或dog类的实例放入队列中
- 调用pollAll方法，将队列中所有的实例按照进队列的先后顺序依次弹出
- 调用pollDog方法，将队列中dog类的实例按照进队列的先后顺序依次弹出
- 调用pollCat方法，将队列中cat类的实例按照进队列的先后顺序依次弹出
- 调用isEmpty方法，判断队列是否为空
- 调用isDogEmpty方法，判断队列中是否还有dog类的实例
- 调用isCatEmpty方法，判断队列中是否还有cat类的实例
思路：将不同的实例盖上时间戳的方法，但是又不能改变用户本身的类。即这个时间戳就是一个不断累加的数据项，用来表示实例进队列的时间，同时由两个队列，一个只放dog类的实例的队列dogQ，一个只放cat类的实例的队列catQ。在实现pollAll方法时，由于有一个表示进队列时间的数据项，因此比较这个数据项的大小即可。
public class Pet {
private String type;
public Pet(String type) {
this.type = type;
}
public String getPetType() {
return this.type;
}
}
Pet类
public class Dog extends Pet {
public Dog() {
super("dog");
}
}
Dog类
public class Cat extends Pet {
public Cat() {
super("cat");
}
}
Cat类
public class PetEnterQueue {
private Pet pet;
private long count;
public PetEnterQueue(Pet pet, long count) {
this.count = count;
this.pet = pet;
}
public Pet getPet() {
return pet;
}
public long getCount() {
return count;
}
public String getEnterType() {
return this.pet.getPetType();
}
}
不改变Pet、Dog、Cat类结构的类并且增加了计数器的PetEnterQueue类
package Chapter1; import java.util.LinkedList;
import java.util.Queue; public class DogCatQueue { private Queue<PetEnterQueue> dogQ;
private Queue<PetEnterQueue> catQ;
private long count; public DogCatQueue() {
this.dogQ = new LinkedList<>();
this.catQ = new LinkedList<>();
this.count = 0;
} public void add(Pet pet) {
if (pet.getPetType().equals("dog")) {
dogQ.add(new PetEnterQueue(pet, count++));
} else if (pet.getPetType().equals("cat")) {
catQ.add(new PetEnterQueue(pet, count++));
} else {
throw new RuntimeException("null pet");
}
} 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("null queue");
}
} public Dog pollDog() {
if (!dogQ.isEmpty()) {
return (Dog) dogQ.poll().getPet();
} else {
throw new RuntimeException("null queue");
}
} public Cat pollCat() {
if (!catQ.isEmpty()) {
return (Cat) catQ.poll().getPet();
} else {
throw new RuntimeException("null queue");
}
} public boolean isEmpty() {
return dogQ.isEmpty() && catQ.isEmpty();
} public boolean isDogEmpty() {
return dogQ.isEmpty();
} public boolean isCatEmpty() {
return catQ.isEmpty();
}
}
DogCatQueue
六、生成窗口最大值数组
题目：有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，每次向右滑动一个位置，如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口，求这些窗口的最大值。
例如：数组[4,3,5,4,3,3,6,7]，w=3时，有435,354,543,433,336,367，则返回{5,5,5,4,6,7}
思路：常规做法的时间复杂度为O(N×w)，而本题要求使用时间复杂度为O(N)的解法
解法：O(N)关键在于利用双端队列来实现窗口最大值的更新。双端队列qmax中存放数组arr的下标。然后遍历到arr[i]时，
入队列：（1）如果qmax为空，直接把下标i放入队列。放入过程结束（2）如果qmax不为空，取出当前qmax队尾存放的下标，记为j：如果arr[j]>arr[i]，则直接把i放进qmax的队尾，放入过程结束；如果arr[j]<=arr[i]，把j从qmax中弹出，继续qmax的放入。
出队列：如果qmax队头的下标等于i-w，说明当前qmax队头的下标已过期，弹出当前队头的下标即可。
例如，[4,3,5,4,3,3,6,7]，w=3
1.qmax为空，qmax：
2.arr[0]=4,qmax:0
3.arr[1]=3,队尾为0，arr[0]>arr[1]，则1放入队尾：1 0
4.arr[2]=5,队尾为1，arr[1]<=arr[2],1弹出，队尾为0，arr[0]<=arr[2]，0弹出，2入，当前qmax：2。此时队头下标为2，所以窗口arr[0...2]的最大值就是arr[2]
5.arr[3]=4,队尾为2，arr[2]>arr[3],则3放入队尾：3 2，此时队头为2，则arr[1...3]的最大值就是arr[2]
6.arr[4]=3,队尾为3，arr[3]>arr[4],则4放入队尾：4 3 2，此时队头为2，则arr[2...4]的最大值就是arr[2]
7.arr[5]=3,队尾为4，arr[4]<=arr[5],4弹出，队尾为3，arr[3]>arr[5],则5让如队尾：5 3 2，此时队头为2，由于i=5,5-w=2，因此2已经过期，弹出2，此时：5 3，队头为3，因此arr[3...5]最大值就是arr[3]
8.arr[6]=6,队尾为5，arr[5]<=arr[6],5弹出，队尾为3，arr[3]<=arr[6]，3弹出，此时队列为空，6入队列：6，此时arr[4...6]的最大值就是arr[6]
9.arr[7]=7,队尾为6，arr[6]<=arr[7],6弹出，队列为空，7入队列，此时arr[5...7]的最大值就是arr[7
根据执行过程可以知道，每个下标最多进qmax一次，出qmax一次，所以遍历的过程进出双端队列的时间复杂度是O(N)，整体的时间复杂度也是O(N)
public int[] getMaxWindow(int[] arr, int w) {
if (arr == null || w < 1 || arr.length < w) {
return null;
}
LinkedList<Integer> qmax = new LinkedList<>();
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);
if (qmax.peekFirst() == i - w) {
qmax.pollFirst();
}
if (i >= w - 1) {
res[index++] = arr[qmax.peekFirst()];
}
}
return res;
}
七、构造数组的MaxTree
题目：一个数组的MaxTree的定义是：（1）数组必须没有重复元素（2）包括MaxTree数在内且在其中的每一棵子树上，值最大的节点都是树的头
要求：时间复杂度O(N)，空间复杂度O(N)
思路：
（1）每一个数的父节点是它左边第一个比它大的数和它右边第一个比它大的数中，较小的那个。
（2）如果一个数左边没有比它大的数，右边也没有。也就是说，这个数是整个数组的最大值，那个这个数是MaxTree的头节点。
这是因为：
（1）通过这个方法，所有的数能生成一棵树，这棵树可能不是二叉树，但肯定是一棵树，而不是多棵树
（2）任何一个数的单独一侧，其孩子数量都不能超过1个，最多只会有1个。即任何一个数最多会有2个孩子，而不会有更多。
实现方法：
要想找每个数左边第一个比它大的数，只需从左到右遍历每个数，栈中保持递减序列，新来的数不停地利用Pop出栈顶，直到栈顶比新数大或没有数。
例如：以[3,1,2]为例，3入栈，1比3小，1入栈，确定1左边第一个比它大的数是3。然后2入栈，1比2小，1出栈，2比3小，2入栈，确定2左边第一个比它大的数是3
以arr=[3,4,5,1,2]为例： 5
3：左：无 右：4 / \
4：左：无 右：5 4 2
5：左：无 右：无 / /
1：左：5 右：2 3 1
2：左：5 右：无
代码实现：
public Node getMaxTree(int[] arr) {
Node[] narr = new Node[arr.length];
for (int i = 0; i < arr.length; i++) {
narr[i] = new Node(arr[i]);
}
Stack<Node> stack = new Stack<>();
HashMap<Node, Node> lBigMap = new HashMap<>();
HashMap<Node, Node> rBigMap = new HashMap<>();
for (int i = 0; i < narr.length; i++) {
Node curNode = narr[i];
while ((!stack.isEmpty()) && stack.peek().val < curNode.val) {
popStackSetMap(stack, lBigMap);
}
stack.push(curNode);
}
while (!stack.isEmpty()) {
popStackSetMap(stack, lBigMap);
}
for (int i = narr.length - 1; i != -1; i--) {
Node curNode = narr[i];
while ((!stack.isEmpty()) && stack.peek().val < curNode.val) {
popStackSetMap(stack, rBigMap);
}
stack.push(curNode);
}
while (!stack.isEmpty()) {
popStackSetMap(stack, rBigMap);
}
Node head = null;
for (int i = 0; i < narr.length; i++) {
Node curNode = narr[i];
Node left = lBigMap.get(curNode);
Node right = rBigMap.get(curNode);
if (left == null && right == null) {
head = curNode;
} else if (left == null) {
if (right.left == null) {
right.left = curNode;
} else {
right.right = curNode;
}
} else if (right == null) {
if (left.left == null) {
left.left = curNode;
} else {
left.right = curNode;
}
} else {
Node parent = left.val < right.val ? left : right;
if (parent.left == null) {
parent.left = curNode;
} else {
parent.right = curNode;
}
}
}
return head;
}
public void popStackSetMap(Stack<Node> stack, HashMap<Node, Node> map) {
Node popNode = stack.pop();
if (stack.isEmpty()) {
map.put(popNode, null);
} else {
map.put(popNode, stack.peek());
}
}
getMaxTree方法
分析过程：
以[3,4,5,1,2]为例，popStackSetMap的作用是栈stack的栈顶出栈记为popNode，如果此时栈为空，则put(popNode,null);否则put(popNode,stack.peek());
第一个for循环，从左往右遍历，
节点3入栈；
节点4大于节点3，3出栈，lBigMap：3-null,4入栈；
节点5大于节点4，4出栈，lBigMap：4-null,5入栈；
节点1入栈；
节点2大于节点1，1出栈，lBigMap：1-5,2入栈
第一个while循环，lBigMap增加2-5,5-null，此时lBigMap：3-null，4-null，5-null，1-5，2-5表示每个数左边第一个比自己大的数
同理：rBigMap：3-4,4-5,5-null,1-2,2-null,表示每个数右边第一个比自己大的数
然后开始创建二叉树的过程...
八、求最大子矩阵的大小
问题：给定一个整型矩阵map，其中的值只有0和1，求其中全是1的所有矩阵区域中，最大的矩阵区域为1的数量
例如：1 1 1 0返回3，
1 0 1 1
1 1 1 1
1 1 1 0 返回6
思路：
第一步：以每一行做切割，统计以当前行作为底的情况下，每个位置往上的1的连续的1的数量。使用高度数组height来表示
例如：第一行做切割后height={1,0,1,1}，第二行做切割后height={2,1,2,2}，第三行做切割后height={3,2,3,2}。即height[j]=map[i][j]==0 ? 0 : height[j]+1
第二步：对于每一次切割，都利用height数组来求出以每一行为底的情况下，最大的矩形是什么。
例如：第一行最大矩形为2，第二行最大矩形为4，第三行最大矩形为6。
关键在于第二步，实质就是求一个直方图中最大矩形的面积。可以求出每一根柱子扩展出去的最大矩形，其中最大的就是要求的。
例如：{3,2,3,0}，画成直方图就是四个柱子的高度分为为3,2,3,0。那么思路就是：（1）第1根柱子右边是2，比3小，无法向右扩展，因此第1根柱子为高度的矩形面积就是3*1=3（2）第2根高度为2的柱子，可以向左扩1个，向右扩1个，面积就是2*3=6（3）第3根没法扩展，面积为3*1=3（4）第4根没法扩展，面积为0*1=0
求上面问题的实质就是，找到左边刚比它矮的柱子位置在哪里，右边刚比它矮的柱子位置在哪里。
解法：
（1）栈为空，直接把i压入栈
（2）只有当前i位置的值height[i]大于当前栈顶元素的值height[stack.peek()]时，i才可以入栈。因此，stack中从栈顶到栈底对应的height是一次递减的。
（3）如果当前的height[i]<=height[stack.peek()]，则弹出栈顶位置，记为j，然后将新的栈顶记为k，即需要考虑位置j
1.对于位置j的柱子来说，向右最远能扩到哪里
（1）如果height[j]>height[i]，那么i-1位置就是向右能扩到的最远位置，因为j之所以被弹出，就是因为遇到了第一个比j位置值小的位置
（2）如果height[j]==height[i]，那么i-1位置不一定是向右能扩到的最远位置，只是起码能扩到的位置。但是可以肯定的是，在这种情况下，i位置的柱子向左必 然也可以扩到j位置。也就是说，j位置的柱子扩出来的最大矩形和i位置的柱子扩出来的最大矩形是同一个。所以此时可以不用再计算j位置的柱子能扩出来的 最大矩形，因为位置i肯定要压入栈中，那就等到位置i弹出的时候再说。
2.对于位置j的柱子来说，向左最远能扩到哪里
肯定是k+1位置。
（1）因为，height[k+1...j-1]之间不可能有小于或等于height[k]的值，否则k位置早从栈里弹出了。
（2）然后因为在栈里k位置和j位置原本是相邻的，并且从栈顶到栈底的位置所代表的值是依次递减并且无重复的，所以在height[k+1...j-1]之间不可能有大于或 等于height[k]同时又小于或等于height[j]的，因为如果有这样的值，k和j在栈中就不可能相邻。
（3）所以，height[k+1...j-1]之间的值必然是即大于height[k]，又大于height[j]的，所以j位置向左最远可以扩到k+1位置
3.综上，j位置的柱子能扩出来的最大矩形为【(i-1) - (k+1) + 1】* height[j] = (i-k-1)*height[j]。
（例如，i=4，j=3，k=0时，第3根柱子向左最远能到(k+1)=1，向右最远能到(i-1)=3，即从第1根到第3根柱子就是第3根柱子扩展出去的最大矩形）
（4）重复执行操作（3），直到某一个栈顶所代表的值小于height[i]，然后把i压入栈中。
以height={3,4,5,4,3,6}为例
生成一个栈stack，从左到右遍历数组：
1.i=0，栈为空，直接将0压入栈中
2.i=1，height[1]>height[0],1入栈，此时：1,0
3.i=2，height[2]>height[1],2入栈，此时：2,1,0
4.i=3，height[3]<=height[2],2出栈，j=2，栈顶为1，k=1，位置2扩出来的最大矩形面积为(3-1-1)*5=5
height[3]<=height[1],1出栈，j=1，栈顶为0，k=0，位置1扩出来的最大矩形面积为(3-0-1)*4=8，比实际偏小，待修正
height[3]>height[0],3入栈，此时：3 0
5.i=4，height[4]<=height[3],3出栈，j=3，栈顶为0，k=0，位置3扩出来的最大矩形面积为(4-0-1)*4=12,这个最大面积也是位置1扩出来的最大矩形面积，被修正了
height[4]<=height[0],0出栈，j=-0，栈为空，k=-1，位置0扩出来的最大矩形面积为(4-(-1)-1)*3=12,比实际偏小，待修正，4入栈，此时：4
6.i=5，height[5] > height[4],5入栈，此时：5 4，此时无法向右扩，可以认为i=6，height[6]极小
7.i=6，height[6]<=height[5],5出栈，j=5，栈顶为4，k=4，位置5扩出来的最大矩形面积为(6-4-1)*6=1
height[6]<=height[4],4出栈，j=4，栈为空，k=-1，位置4扩出来的最大面积为(6-(-1)-1)*3=18
8.栈为空，过程结束，返回18
代码实现：1.maxRecFromBottom方法，就是上面的8步所执行的方法
public int maxRecFromBottom(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int maxArea = 0;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < height.length; i++) {
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(maxArea, curArea);
}
stack.push(i);
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(maxArea, curArea);
}
}
return maxArea;
}
代码实现2：总的方法
public 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(maxArea, maxRecFromBottom(height));
}
return maxArea;
}
九、最大值减去最小值小于或等于num的子数组数量
问题：给定数组arr和整数num，共返回有多少个子数组满足：max(arr[i...j]) - min(arr[i...j]) <= num
要求：如果数组长度为N，实现时间复杂度为O(N)的解法
思路：
1.普通解法：找到arr的所有子数组，一共有O(N2)个，然后对每一个子数组做遍历找到其中的最大值和最小值，遍历的过程时间复杂度为O(N)，则总时间复杂度为O(N3)
2.最优解法（时间复杂度为O(N) + 空间复杂度为O(N)）：类似之前做过的“滑动窗口”的问题，同样使用双端队列。生成两个双端队列qmax和qmin。当子数组为arr[i...j]时，qmax维护了窗口子数组arr[i...j]的最大值更新，qmin维护了窗口子数组arr[i...j]的最小值更新。当子数组arr[i...j]变成arr[i...j+1]时，qmax和qmin可以在O(1)时间内更新，并且可以在O(1)时间内得到arr[i...j+1]的最大值和最小值。同理，变成arr[i+1...j]也一样。
分析题目可以得到两个结论：
1.如果arr[i...j]满足max(arr[i...j]) - min(arr[i...j]) <= num，那么arr[i...j]中的每一个子数组即arr[k...l](i<=k<=l<=j)都满足条件。例如：arr[i...j-1]的最大值只可能小于等于arr[i...j]的最大值，同理其最小值也只能小于等于arr[i...j]的最小值，所以arr[i...j-1]必满足条件。
2.如果arr[i...j]不满足条件，那么所有包含arr[i...j]的子数组arr[k...l](k<=i<=j<=l)都不满足条件。
解法：
1.生成两个双端队列qmax和qmin，生成两个整型变量i和j表示子数组的范围，生成整型变量res表示所有满足条件的子数组数量。
2.令j不断向右移动，并不断更新qmax和qmin。一旦出现arr[i..j]不满足条件的情况，j向右扩停止，此时arr[i...j-1]、arr[i...j-2]、arr[i...i]必定都是满足的，即此时在以i开头的子数组中，满足条件的右j-i个，即令res+=j-i
3.令i向右移动一个位置，即arr[i+1...j]，然后重复步骤2，统计所有以i+1开头的子数组中满足条件的。
public int getNum(int[] arr, int num) {
if (arr == null || arr.length == 0) {
return 0;
}
LinkedList<Integer> qmin = new LinkedList<>();
LinkedList<Integer> qmax = new LinkedList<>();
int i = 0;
int j = 0;
int res = 0;
while (i < arr.length) {
while (j < arr.length) {
while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[j]) {
qmin.pollLast();
}
qmin.addLast(j);
while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[j]) {
qmax.pollLast();
}
qmax.addLast(j);
if (arr[qmax.getFirst()] - arr[qmin.getFirst()] > num) {
break;
}
j++;
}
if (qmin.peekFirst() == i) {
qmin.pollFirst();
}
if (qmax.peekFirst() == i) {
qmax.pollFirst();
}
res += j - i;
i++;
}
return res;
}
最新文章
- Web前端知识技能大汇总
- 主流Web服务器一览
- convert Timestamp to Real time
- 1.VS2010C++环境设置
- Environment variable ORACLE_UNQNAME not defined. Please set ORACLE_UNQNAME to database unique name. 的解决方法
- oracle 分区表和分区索引
- ACM HDU 2674 N! Again(数论)
- C++格式化字符函数
- slime+sbcl for common lisp
- visio 2013 破解工具 - KMSpico
- UVa 341 - Non-Stop Travel
- 使用DateTimeOffset 对xml中的日期时间格式时区进行处理
- python更新数据库脚本两种方法
- Android 热补丁实践之路
- PLSQL僵死
- GNOME图形界面的基本操作
- FFMPEG系列课程（一）打开视频解码器
- webpack+vue+es6+postcss
- Codeforces 954 E. Water Taps
- 007-js中的Array常用方法