栈:先进后出
stack:添加和删除为O(1),查询为O(n)
队列:先进先出
queue:添加和删除为O(1),查询为O(n)
示例代码-Stack
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
System.out.println(stack);
System.out.println(stack.search(4));
stack.pop();
stack.pop();
Integer topElement = stack.peek();
System.out.println(topElement);
System.out.println("3的位置"+stack.search(3));
示例代码-Queue
Queue<String> queue = new LinkedList<String>();
queue.offer("one");
queue.offer("two");
queue.offer("three");
queue.offer("four");
System.out.println(queue);
String polledElement = queue.poll();
System.out.println(polledElement);
System.out.println(queue);
String peekedElement = queue.peek();
System.out.println(peekedElememt);
System.out.println(queue);
while(queue.size()>0){
System.out.println(queue.poll());
}
示例代码-Deque
Deque<String> deque = new LinkedList<String>();
deque.push("a");
deque.push("b");
deque.push("c");
System.out.println(deque);
String str = deque.peek();
System.out.println(str);
System.out.println(deque);
while(deque.size()>0){
System.out.println(deque.pop());
}
System.out.println(deque);
Priority Queue
- 1.插入操作:O(1);
- 2.取出操作:O(logN)-按照元素的优先级取出
- 3.底层具体实现的数据结构较为多样和复杂:heap
Java源码分析:
Stack:http://develop.classpath.org/doc/java/util/Stack-source.html
Queue:http://fuseyism.com/classpath/doc/java/util/Queue-source.html
作业:分析Queue和Priority Queue的源码
柱状图中最大矩形
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
1.暴力法
class Solution {
public int largestRectangleArea(int[] heights) {
int length = heights.length;
int maxArea = 0;
for(int left = 0;left < length;left++){
int minHeight = Integer.MAX_VALUE;
for(int right = left;right < length;right++){
minHeight = Math.min(minHeight,heights[right]);
maxArea = Math.max(maxArea,minHeight * (right - left + 1));
}
}
return maxArea;
}
}
2.栈
维护一个栈，一开始，把-1放进栈的顶部来表示开始。初始化时，按照从左到右的顺序，不断将柱子的需要放进栈中，知道遇到相邻柱子呈下降关系，也就是a[i-1]>a[i]。现在我们开始将栈中的序号弹出，知道遇到stack[j]满足a[stack[j]]<= a[i]。每次我们弹出下标时，我们用弹出元素作为高形成的最大面积矩形的宽是当前元素与stack[top - 1]之间的那些柱子。也就是当我们淡出stack[top]时，记当前元素在原数组中的下标为i,当前弹出元素为高的最大矩形面积为:
(i - stack[top - 1] - 1) * a[stack[top]]
public int largestRectangleArea1(int[] heights) {
Stack<Integer> stack = new Stack<>();
stack.push(-1);
int maxarea = 0;
for (int i=0;i<heights.length;++i){
while (stack.peek() != -1 && heights[stack.peek()] >= heights[i])
maxarea = Math.max(maxarea,heights[stack.pop()] * (i - stack.peek() -1));
stack.push(i);
}
while (stack.peek() != -1){
maxarea = Math.max(maxarea,heights[stack.pop()] * (heights.length-1-stack.peek()));
}
return maxarea;
}
3.单调栈
以上暴力写法 Java 可以通过，但我们不妨想一下这里的双重循环是否可以优化？
我们每遍历到当前柱体 i 时：
上述写法中，我们需要再嵌套一层 while 循环来向左找到第一个比柱体 i 高度小的柱体，这个过程是 O(N)O(N) 的；
那么我们可以 O(1)O(1) 的获取柱体 i 左边第一个比它小的柱体吗？答案就是单调增栈，因为对于栈中的柱体来说，栈中下一个柱体就是左边第一个高度小于自身的柱体。
因此做法就很简单了，我们遍历每个柱体，若当前的柱体高度大于等于栈顶柱体的高度，就直接将当前柱体入栈，否则若当前的柱体高度小于栈顶柱体的高度，说明当前栈顶柱体找到了右边的第一个小于自身的柱体，那么就可以将栈顶柱体出栈来计算以其为高的矩形的面积了。
class Solution {
public int largestRectangleArea(int[] heights) {
// 这里为了代码简便，在柱体数组的头和尾加了两个高度为 0 的柱体。
int[] tmp = new int[heights.length + 2];
System.arraycopy(heights, 0, tmp, 1, heights.length);
Deque<Integer> stack = new ArrayDeque<>();
int area = 0;
for (int i = 0; i < tmp.length; i++) {
// 对栈中柱体来说，栈中的下一个柱体就是其「左边第一个小于自身的柱体」；
// 若当前柱体 i 的高度小于栈顶柱体的高度，说明 i 是栈顶柱体的「右边第一个小于栈顶柱体的柱体」。
// 因此以栈顶柱体为高的矩形的左右宽度边界就确定了，可以计算面积🌶️ ～
while (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]) {
int h = tmp[stack.pop()];
area = Math.max(area, (i - stack.peek() - 1) * h);
}
stack.push(i);
}
return area;
}
}
滑动窗口最大值
https://leetcode-cn.com/problems/sliding-window-maximum/
1.暴力法
最简单直接的方法是遍历每个滑动窗口，找到每个窗口的最大值。一共有 N - k + 1 个滑动窗口，每个有 k 个元素，于是算法的时间复杂度为 {O}(N k)O(Nk)，表现较差。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n * k == 0) return new int[0];
int [] output = new int[n - k + 1];
for (int i = 0; i < n - k + 1; i++) {
int max = Integer.MIN_VALUE;
for(int j = i; j < i + k; j++)
max = Math.max(max, nums[j]);
output[i] = max;
}
return output;
}
}
复杂度分析
时间复杂度：{O}(N k)O(Nk)。其中 N 为数组中元素个数。
空间复杂度：{O}(N - k + 1)O(N−k+1)，用于输出数组。
2.双端队列
class Queue {
void push(int n);
// 或 enqueue，在队尾加入元素 n
void pop();
// 或 dequeue，删除队头元素
}
class MonotonicQueue {
// 在队尾添加元素 n
void push(int n);
// 返回当前队列中的最大值
int max();
// 队头元素如果是 n，删除它
void pop(int n);
}
class deque {
// 在队头插入元素 n
void push_front(int n);
// 在队尾插入元素 n
void push_back(int n);
// 在队头删除元素
void pop_front();
// 在队尾删除元素
void pop_back();
// 返回队头元素
int front();
// 返回队尾元素
int back();
}
public int[] maxSlidingWindow(int[] a, int k) {
if (a == null || k <= 0) {
return new int[0];
}
int n = a.length;
int[] r = new int[n-k+1];
int ri = 0;
// store index
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < a.length; i++) {
// remove numbers out of range k
while (!q.isEmpty() && q.peek() < i - k + 1) {
q.poll();
}
// remove smaller numbers in k range as they are useless
while (!q.isEmpty() && a[q.peekLast()] < a[i]) {
q.pollLast();
}
// q contains index... r contains content
q.offer(i);
if (i >= k - 1) {
r[ri++] = a[q.peek()];
}
}
return r;
}
预习题目
有效的括号
https://leetcode-cn.com/problems/valid-parentheses/
//有效的括号
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (Character c:s.toCharArray()){
if (c == '(') stack.push(')');
else if(c == '[') stack.push(']');
else if(c == '{') stack.push('}');
else if(stack.isEmpty()|| stack.pop() != c) return false;
}
return stack.isEmpty();
}
最小栈
https://leetcode-cn.com/problems/min-stack/
class MinStack {
Stack<Integer> stack;
Stack<Integer> minStack;
public MinStack(){
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int n){
stack.push(n);
if(minStack.isEmpty() || n <= minStack.peek())
minStack.push(n);
}
public void pop(){
if(stack.pop().equals(minStack.peek()))
minStack.pop();
}
public int top(){
return stack.peek();
}
public int getMin(){
return minStack.peek();
}
}
课后作业
设计循环双端队列
https://leetcode-cn.com/problems/design-circular-deque/
设计实现双端队列。
你的实现需要支持以下操作：
MyCircularDeque(k)：构造函数,双端队列的大小为k。
insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true。
insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。
deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true。
deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。
getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。
getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1。
isEmpty()：检查双端队列是否为空。
isFull()：检查双端队列是否满了。
示例：
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1); // 返回 true
circularDeque.insertLast(2); // 返回 true
circularDeque.insertFront(3); // 返回 true
circularDeque.insertFront(4); // 已经满了，返回 false
circularDeque.getRear(); // 返回 2
circularDeque.isFull(); // 返回 true
circularDeque.deleteLast(); // 返回 true
circularDeque.insertFront(4); // 返回 true
circularDeque.getFront(); // 返回 4
提示：
所有值的范围为 [1, 1000]
操作次数的范围为 [1, 1000]
请不要使用内置的双端队列库
public class MyCircularDeque {
// 1、不用设计成动态数组，使用静态数组即可
// 2、设计 head 和 tail 指针变量
// 3、head == tail 成立的时候表示队列为空
// 4、tail + 1 == head
private int capacity;
private int[] arr;
private int front;
private int rear;
public MyCircularDeque(int k){
capacity = k + 1;
arr = new int[capacity];
// 头部指向第 1 个存放元素的位置
// 插入时，先减，再赋值
// 删除时，索引 +1（注意取模）
front = 0;
// 尾部指向下一个插入元素的位置
// 插入时，先赋值，再加
// 删除时，索引 -1（注意取模）
rear = 0;
}
public boolean insertFront(int value){
if (isFull()){
return false;
}
front = (front -1 + capacity)%capacity;
arr[front] = value;
return true;
}
public boolean insertLast(int value){
if(isFull()){
return false;
}
arr[rear] = value;
rear = (rear + 1)% capacity;
return true;
}
public boolean deleteFront(){
if (isEmpty())
return false;
// front 被设计在数组的开头，所以是 +1
front = (front + 1) % capacity;
return true;
}
public boolean deleteLast(){
if (isEmpty()) return false;
// rear 被设计在数组的末尾，所以是 -1
rear = (rear - 1 + capacity) % capacity;
return true;
}
public int getFront(){
if (isEmpty()) return -1;
return arr[front];
}
public int getRear(){
if (isEmpty()) return -1;
// 当 rear 为 0 时防止数组越界
return arr[(rear -1 + capacity) % capacity];
}
public boolean isEmpty(){
return front == rear;
}
public boolean isFull(){
// 注意：这个设计是非常经典的做法
return (rear+1) %capacity == front;
}
}
接雨水
https://leetcode-cn.com/problems/trapping-rain-water/
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
接雨水.png
方法一:暴力法
直观想法
直接按问题描述进行。对于数组中的每个元素，我们找出下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值。
算法
初始化 ans=0ans=0
从左向右扫描数组：
初始化 \text{max_left}=0max_left=0 和 \text{max_right}=0max_right=0
从当前元素向左扫描并更新：
\text{max_left}=\max(\text{max_left},\text{height}[j])max_left=max(max_left,height[j])
从当前元素向右扫描并更新：
\text{max_right}=\max(\text{max_right},\text{height}[j])max_right=max(max_right,height[j])
将\min(\text{max_left},\text{max_right}) - \text{height}[i]min(max_left,max_right)−height[i] 累加到 \text{ans}ans
public int requireRain(int[] nums) {
int ans = 0;
for (int i = 0; i < nums.length; i++) {
int max_left = 0, max_right = 0;
for (int j = i ; j >= 0; j--) {
max_left = Math.max(max_left, nums[j]);
}
for (int k = i; k < nums.length; k++) {
max_right = Math.max(nums[k], max_right);
}
ans += (Math.min(max_left, max_right) - nums[i]);
}
return ans;
}
方法二:栈
直观想法
我们可以不用像方法 2 那样存储最大高度，而是用栈来跟踪可能储水的最长的条形块。使用栈就可以在一次遍历内完成计算。
我们在遍历数组时维护一个栈。如果当前的条形块小于或等于栈顶的条形块，我们将条形块的索引入栈，意思是当前的条形块被栈中的前一个条形块界定。如果我们发现一个条形块长于栈顶，我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定，因此我们可以弹出栈顶元素并且累加答案到 \text{ans}ans 。
算法
使用栈来存储条形块的索引下标。
遍历数组：
当栈非空且 \text{height}[current]>\text{height}[st.top()]height[current]>height[st.top()]
意味着栈中元素可以被弹出。弹出栈顶元素 \text{top}top。
计算当前元素和栈顶元素的距离，准备进行填充操作
\text{distance} = \text{current} - \text{st.top}() - 1distance=current−st.top()−1
找出界定高度
\text{bounded_height} = \min(\text{height[current]}, \text{height[st.top()]}) - \text{height[top]}bounded_height=min(height[current],height[st.top()])−height[top]
往答案中累加积水量\text{ans} \mathrel{+}= \text{distance} \times \text{bounded_height}ans+=distance×bounded_height
将当前索引下标入栈
将 \text{current}current 移动到下个位置
public int requireRain0(int[] nums) {
int ans = 0;
int currentIndex = 0;
Stack<Integer> stack = new Stack<>();
while (currentIndex < nums.length){
while (!stack.isEmpty() && nums[currentIndex] > nums[stack.peek()]){
int top = stack.peek();
stack.pop();
if (stack.isEmpty())
break;
int distance = currentIndex - stack.peek() - 1;
int boundHight = Math.min(nums[currentIndex],nums[stack.peek()])-nums[top];
ans += distance*boundHight;
}
stack.push(currentIndex++);
}
return ans;
}
方法三:双指针
直观想法
想办法一次完成遍历。
我们注意到，只要 \text{right_max}[i]>\text{left_max}[i]right_max[i]>left_max[i] （元素 0 到元素 6），积水高度将由 left_max 决定，类似地 \text{left_max}[i]>\text{right_max}[i]left_max[i]>right_max[i]（元素 8 到元素 11）。
所以我们可以认为如果一端有更高的条形块（例如右端），积水的高度依赖于当前方向的高度（从左到右）。当我们发现另一侧（右侧）的条形块高度不是最高的，我们则开始从相反的方向遍历（从右到左）。
我们必须在遍历时维护 \text{left_max}left_max 和 \text{right_max}right_max ，但是我们现在可以使用两个指针交替进行，实现 1 次遍历即可完成。
算法
初始化 \text{left}left 指针为 0 并且 \text{right}right 指针为 size-1
While \text{left}< \text{right}left<right, do:
If \text{height[left]}height[left] < \text{height[right]}height[right]
If \text{height[left]} \geq \text{left_max}height[left]≥left_max, 更新 \text{left_max}left_max
Else 累加 \text{left_max}-\text{height[left]}left_max−height[left] 到 \text{ans}ans
\text{left}left = \text{left}left + 1.
Else
If \text{height[right]} \geq \text{right_max}height[right]≥right_max, 更新 \text{right_max}right_max
Else 累加 \text{right_max}-\text{height[right]}right_max−height[right] 到 \text{ans}ans
\text{right}right = \text{right}right - 1.
C++
int Solution::trap(std::vector<int>& height)
{
int left = 0,right = height.size()-1;
int left_max = 0,right_max = 0;
int ans = 0;
while (left < right) {
if (height[left] < height[right]) {
height[left] >= left_max ? left_max = height[left]: ans += (left_max-height[left]);
left++;
}else{
height[right] >= right_max ? right_max = height[right] : ans += (right_max - height[right]);
right--;
}
}
return ans;
}
Java
public int trap(int[] height){
int left = 0,right = height.length - 1;
int left_max = 0,right_max = 0;
int ans = 0;
while (left < right){
if (height[left] < height[right]){
if(height[left] >= left_max){
left_max = height[left];
} else {
ans += (left_max - height[left]);
}
left++;
}else {
if (height[right] >= right_max){
right_max = height[right];
}else{
ans += (right_max - height[right]);
}
right--;
}
}
return ans;
}
网友评论