队列中可以看到的人
队列中可以看到的人
通过栈维护后面元素的可以看到的人的集合,候选集
对于当前元素,所有栈顶元素更小的都是当前元素可以看到的,栈为单调递减栈
class Solution {
public int[] canSeePersonsCount(int[] heights){
int n=heights.length;
int[] res=new int[n];
Stack<Integer> stack=new Stack<Integer>();
for(int i=n-1;i>=0;i--){
while (!stack.isEmpty()) {
res[i]++;//栈顶元素可以看见。无论是比当前元素高还是低都可以看见
if(heights[i]>heights[stack.peek()]){
stack.pop();
}else{
break;
}
}
stack.push(i);
}
return res;
}
}
和至少为k的最短子数组
数组元素存在负值,不具有单调性,对于leetcode209题,数组元素都为正整数,具有单调性,可以通过双指针
长度最小的子数组
前缀和枚举所有的子数组,超时
单调性,对于当前前缀prefix[i] 如果之前更大的前缀prefix[j]可以与之后的前缀作为结果,当前前缀prefix[i]可以得到更大差值,并且区间长度更短,
每次通过最早的元素进行更新,更新之后之后的前缀更新不能保证最有区间长度
class Solution {
public int shortestSubarray(int[] nums, int k) {
int n=nums.length;
Deque<Integer> queue=new ArrayDeque<Integer>();
long[] prefix=new long[n+1];
for(int i=1;i<=n;i++){
prefix[i]=prefix[i-1]+nums[i-1];
}
queue.offer(0);
int res=Integer.MAX_VALUE;
for(int i=1;i<=n;i++){
while(!queue.isEmpty()&&prefix[queue.peekFirst()]+k<=prefix[i]){
//更新答案
res=Math.min(res,i-queue.peekFirst());
queue.pollFirst();
}
//维护单调性
while(!queue.isEmpty()&&prefix[queue.peekLast()]>=prefix[i]){
queue.pollLast();
}
queue.offerLast(i);
}
return res==Integer.MAX_VALUE? -1:res;
}
}
长度最小的子数组
长度最小的子数组
滑动窗口
class Solution {
public int minSubArrayLen(int target, int[] nums) {
//通过双指针
int res=Integer.MAX_VALUE;
int sum=0;
for(int i=0,j=0;i<nums.length;i++){
sum+=nums[i];
while(sum>=target){
res=Math.min(res,i-j+1);
sum-=nums[j++];
}
}
return res==Integer.MAX_VALUE? 0:res;
}
}
车队
车队
单调栈,栈顶元素是当前元素会在右边碰撞的元素位置
class Solution {
public double[] getCollisionTimes(int[][] cars){
int n=cars.length;
Stack<Integer> stack=new Stack<Integer>();
double[] res=new double[n];
for(int i=n-1;i>=0;i--){
while (!stack.isEmpty()) {
//如果栈顶小车不能碰撞
if(cars[stack.peek()][1]>=cars[i][1]){
stack.pop();
}else{
if(res[stack.peek()]<0){
//当前栈顶就是碰撞
break;
}else{
if(((double)(cars[stack.peek()][0]-cars[i][0]))/((double)(cars[i][1]-cars[stack.peek()][1]))<=res[stack.peek()]){
//
break;
}else{
stack.pop();
}
}
}
}
if (stack.isEmpty()) {
res[i]=-1;
}else{
res[i]=((double)(cars[stack.peek()][0]-cars[i][0])/(double)(cars[i][1]-cars[stack.peek()][1]));
}
//将当前小车加入栈
stack.push(i);
}
return res;
}
}
带限制的最大子序列和
带限制的最大子序列和
超时解法,定义dp[i]为子序列以nums[i]结尾,即子序列选择元素nums[i]
状态转移分为只包含nums[i],以及从前面最大非负dp[j],且i-j<=k元素转移
但是因为k数据范围较大,第二个for超时,通过单调队列进行优化
class Solution {
public static int constrainedSubsetSum(int[] nums, int k) {
//通过dp
int n=nums.length;
int[] dp=new int[n];
for(int i=0;i<nums.length;i++){
dp[i]=nums[i];
}
for(int i=0;i<n;i++){
System.out.print(dp[i]+" ");
}
System.out.println();
for(int i=1;i<n;i++){
for(int j=i-1;j>=i-k&&j>=0;j--){
dp[i]=Math.max(dp[i],Math.max(0,dp[j])+nums[i]);
}
}
for(int i=0;i<n;i++){
System.out.print(dp[i]+" ");
}
int res=Integer.MIN_VALUE;
for(int i=0;i<n;i++){
res=Math.max(res,dp[i]);
}
return res;
}
}
方式二:单调队列优化
创建双端队列,通过双端队列接口进行接收
Deque<Integer> queue=new ArrayDeque<Integer>();
Deque<Integer> queueu=new LinkedList<Integer>();
通过双端队列维护
(1)维护双端队列元素,取元素
(2)计算逻辑
(3)将元素加入双端队列,维护单调性,单调队列
public int constrainedSubsetSum(int[] nums, int k) {
int n=nums.length;
int[] dp=new int[n];
for(int i=0;i<n;i++){
dp[i]=nums[i];
}
//单调队列
Deque<Integer> queue=new LinkedList<>();
// Deque<Integer> queue=new ArrayDeque<>();//ArrayDeque通过数组实现双端队列
queue.offer(0);
for(int i=1;i<n;i++){
//下标超过k出队
while(!queue.isEmpty()&&i-queue.peekFirst()>k){
queue.pollFirst();
}
//转移
dp[i]=Math.max(0,dp[queue.peekFirst()])+nums[i];
//当前加入队列
//维护单调性
while(!queue.isEmpty()&&dp[queue.peekLast()]<=dp[i]){
queue.pollLast();
}
queue.offerLast(i);
}
int res=Integer.MIN_VALUE;
for(int i=0;i<n;i++){
res=Math.max(res,dp[i]);
}
return res;
}
叶值的最小代价生成树
//对于一个序列如果要作为二叉树的中序序列,只需要在合并的时候将对应的元素按照对应的顺序进行合并即可
如果需要保证最小代价,考虑对应的递增序列,
如果是递增序列,从左往右进行合并
如果是递减序列,从右往左进行合并
如果是先递增后递减序列,从左往右,在从右往左进行合并单调序列接都可以
如果是先递减后递增序列,需要比较左右端点的最小元素,从较小元素进行合并
class Solution {
public int mctFromLeafValues(int[] arr) {
//只要合并的过程是从左往右的,最终就是作为二叉树的中序序列
//合并的顺序
//对于递增的序列,直接进行合并
int res=0;
Stack<Integer> stack=new Stack<Integer>();
//添加一个边界
stack.push(Integer.MAX_VALUE);
for(int i=0;i<arr.length;i++){
while(arr[i]>=stack.peek()){
//将栈顶元素出栈计算
res+=stack.pop()*Math.min(stack.peek(),arr[i]);
}
stack.push(arr[i]);
}
while(stack.size()>2){
res+=stack.pop()*stack.peek();
}
return res;
}
}
子数组的最小值之和
子数组的最小元素之和
通过枚举每一个元素作为最小元素,左右的边界,找到左边第一个小于当前元素的第一个元素
右边如果对应的元素相等也认为对应的元素,当前元素更大,避免重复计数
//通过单调栈维护前缀和后缀
public static int sumSubarrayMins(int[] arr){
int MOD=1000000007;
int n=arr.length;
int[] prefix=new int[n];
int[] next=new int[n];
Stack<Integer> stack1=new Stack<Integer>();
//对于每一个元素
for(int i=0;i<n;i++){
while(!stack1.isEmpty()&&arr[i]<=arr[stack1.peek()]){
stack1.pop();
}
prefix[i]=stack1.isEmpty()? -1:stack1.peek();
//将当前元素加入栈
stack1.push(i);
}
//通过单调栈对后缀进行维护
int[] subfix=new int[n];
stack1.clear();
for(int i=n-1;i>=0;i--){
while(!stack1.isEmpty()&&arr[i]<arr[stack1.peek()]){
stack1.pop();
}
subfix[i]=stack1.isEmpty()? n:stack1.peek();
stack1.push(i);
}
//对于所有的元素进行枚举
long res=0;
for(int i=0;i<n;i++){
res+=(long)(i-prefix[i])*(subfix[i]-i)%MOD*arr[i]%MOD;
res%=MOD;
}
return (int)res;
}
单链表后面第一个更大的元素
class Solution {
public int[] nextLargerNodes(ListNode head) {
//通过维护一个单调递减的栈
Stack<int[]> stack=new Stack<int[]>();
ListNode cur=head;
int[] res=new int[100010];
int count=0;
while(cur!=null){
while(!stack.isEmpty()&&stack.peek()[0]<cur.val){
int[] node=stack.pop();
res[node[1]]=cur.val;
}
//将元素加入站
stack.push(new int[]{cur.val,count++});
cur=cur.next;
}
return Arrays.copyOf(res,count);
}
}