给定一个长度为 的可能含有重复值的数组 ,找到每一个位置 左边最近的位置 和右边最近的位置 , 和 比 小。
请设计算法,返回一个二维数组,表示所有位置相应的信息。位置信息包括:两个数字 和 。如果不存在,则值为 -1,下标从 0 开始。
数据范围: ,
进阶:空间复杂度 ,时间复杂度
[3,4,1,5,6,2,7]
[[-1,2],[0,2],[-1,-1],[2,5],[3,5],[2,-1],[5,-1]]
[1,1,1,1]
[[-1,-1],[-1,-1],[-1,-1],[-1,-1]]
找到比自己的小的左边加上右边的位置维护一个单调递增的栈,栈内元素从栈底到栈顶是单调递增
分别用两次循环,一次寻找左边的一次寻找右边的位置索引
import java.util.*; import java.util.Stack; public class Solution { public int[][] foundMonotoneStack (int[] nums) { int n=nums.length; int [][]ans=new int[n][2]; Stack<Integer> stack=new Stack<>(); for(int i=0;i<n;i++){ while(!stack.isEmpty()&&nums[stack.peek()]>=nums[i]) stack.pop(); if(stack.isEmpty()){ ans[i][0]=-1; } else{ ans[i][0]=stack.peek(); } stack.push(i); } stack.clear(); for(int i=n-1;i>=0;i--){ while(!stack.isEmpty()&&nums[stack.peek()]>=nums[i]) stack.pop(); if(stack.isEmpty()){ ans[i][1]=-1; } else{ ans[i][1]=stack.peek(); } stack.push(i); } return ans; } }
import java.util.*; public class Solution { /** * 使用两次单调递增栈 * * * @param nums int一维数组 * @return int二维数组 */ public static int[][] foundMonotoneStack(int[] nums) { int[][] res = new int[nums.length][2]; Stack<Integer> stack = new Stack<>(); for (int i = 0; i < nums.length; i++) { while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) { stack.pop(); } if (stack.isEmpty()) res[i][0] = -1; else { res[i][0] = stack.peek(); } stack.push(i); } stack.clear(); for (int i = nums.length - 1; i >= 0; i--) { while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) { stack.pop(); } if (stack.isEmpty()) res[i][1] = -1; else { res[i][1] = stack.peek(); } stack.push(i); } return res; } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int一维数组 * @return int二维数组 */ public int[][] foundMonotoneStack (int[] nums) { // write code here int[][] res = new int[nums.length][2]; for(int i = 0; i < nums.length; i++){ res[i][0] = -1; res[i][1] = -1; } Stack<LinkedList<Integer>> stack = new Stack<>(); // 栈底往栈顶保持单调递增 for(int i = 0; i < nums.length; i++){ if(stack.isEmpty()){ LinkedList<Integer> list = new LinkedList<>(); list.add(i); stack.push(list); }else{ if(nums[i] == nums[stack.peek().peekLast()]){ stack.peek().add(i); continue; }else if(nums[i] < nums[stack.peek().peekLast()]){ while(!stack.isEmpty() && nums[i] < nums[stack.peek().peekLast()]){ // 单调性被破坏,开始弹栈生成信息 Iterator<Integer> list = stack.pop().iterator(); while(list.hasNext()){ int curIdx = list.next(); res[curIdx][1] = i; // 栈顶每个元素右边比它小的都是nums[i] // 栈顶每个元素左边比它小是下面压着的数,下面没有压那就是-1 if(!stack.isEmpty()) res[curIdx][0] = stack.peek().peekLast(); else res[curIdx][0] = -1; } } } LinkedList<Integer> list = new LinkedList<>(); list.add(i); stack.push(list); } } // 清算阶段,将栈中所有元素左边比它小的第一个数找到 while(!stack.isEmpty()){ Iterator<Integer> iter = stack.pop().iterator(); while(iter.hasNext()){ if(!stack.isEmpty()) res[iter.next()][0] = stack.peek().peekLast(); else res[iter.next()][0] = -1; } } return res; } }
#include <errno.h> #include <stdbool.h> #define OK 1 #define ERROR -1 #define MEMORY_OVERFLOW -2 #define NOT ! #define DEFAULT_CAPACITY 8 #define InitStack(S) __InitStack(S, DEFAULT_CAPACITY) typedef int Status; // ==================== 顺序栈数据结构表示与实现 ==================== typedef int SElemType; typedef struct { SElemType* base; SElemType* top; size_t capacity; } SqStack; Status __InitStack(SqStack* S, int initialCapacity) { if (initialCapacity < 1) { printf("__InitStack ERROR: The initialCapacity %d Must be > 0!", initialCapacity); return ERROR; } if (!(S->base = (SElemType*) malloc(initialCapacity * sizeof(SElemType)))) { printf("__InitStack Memeory Overflow: %s\n", strerror(errno)); exit(MEMORY_OVERFLOW); } S->top = S->base; S->capacity = initialCapacity; return OK; } bool StackEmpty(SqStack* S) { return S->top == S->base; } bool StackFull(SqStack* S) { return (S->top - S->base) == S->capacity; } size_t StackLength(SqStack* S) { return S->top - S->base; } void __large_capacity(SqStack* S) { if (!(S->base = (SElemType*) realloc(S->base, (S->capacity << 1) * sizeof(SElemType)))) { printf("__large_capacity Memeory Overflow: %s\n", strerror(errno)); exit(MEMORY_OVERFLOW); } S->top = S->base + S->capacity; S->capacity <<= 1; } Status Push(SqStack* S, SElemType e) { if (StackFull(S)) __large_capacity(S); *S->top++ = e; return OK; } Status Pop(SqStack* S, SElemType* ret) { if (StackEmpty(S)) { puts("Pop ERROR: The stack is empty!"); return ERROR; } *ret = *--S->top; return OK; } SElemType GetTop(SqStack* S) { if (StackEmpty(S)) return -0x3F3F3F3F; return *((*S).top - 1); } Status DestroyStack(SqStack* S) { free(S->base); S->top = NULL; return OK; } // ==================== 顺序栈数据结构表示与实现 ==================== /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int一维数组 * @param numsLen int nums数组长度 * @return int二维数组 * @return int* returnSize 返回数组行数 * @return int** returnColumnSizes 返回数组列数 */ int** foundMonotoneStack(int* nums, int numsLen, int* returnSize, int** returnColumnSizes) { SqStack S1, S2; // 创建两个单调递增栈 InitStack(&S1); InitStack(&S2); int i, index; int ** ans = (int**) malloc(numsLen * sizeof(int*)); *returnSize = numsLen; *returnColumnSizes = (int*) malloc(numsLen * sizeof(int)); for (i = 0; i < numsLen; ++i) { *(ans + i) = (int*) malloc(2 * sizeof(int)); memset(*(ans + i), -1, sizeof(*(ans + i))); (*returnColumnSizes)[i] = 2; } for (i = numsLen - 1; i >= 0; --i) { while (NOT StackEmpty(&S1) && *(nums + GetTop(&S1)) > *(nums + i)) { Pop(&S1, &index); *(*(ans + index)) = i; } Push(&S1, i); } for (i = 0; i < numsLen; ++i) { while (NOT StackEmpty(&S2) && *(nums + GetTop(&S2)) > *(nums + i)) { Pop(&S2, &index); *(*(ans + index) + 1) = i; } Push(&S2, i); } DestroyStack(&S1); DestroyStack(&S2); return ans; }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int一维数组 * @return int二维数组 */ public int[][] foundMonotoneStack (int[] nums) { // write code here LinkedList<Integer>stk=new LinkedList<>(); int[][]res=new int[nums.length][2]; for(int i=0;i<nums.length;i++){ while(!stk.isEmpty()&&nums[stk.peekLast()]>=nums[i]){ res[stk.peekLast()][1]=i; stk.pollLast(); } if(!stk.isEmpty()){ res[i][0]=stk.peekLast(); }else res[i][0]=-1; stk.addLast(i); } while(!stk.isEmpty()){ res[stk.pollLast()][1]=-1; } return res; } }
class Solution: def foundMonotoneStack(self , nums ): # write code here n = len(nums) res = [[-1, -1] for _ in range(n)] stack = [] for i in range(n): while stack and nums[stack[-1]] >= nums[i]: # 保证stack里始终从下往上递增的 stack.pop() if not stack: res[i][0] = -1 else: res[i][0] = stack[-1] # 这里stack的最上面比nums[i]小 stack.append(i) # 这里append的值肯定比pop的值要小,所以pop出来的值就没有用了 stack.clear() for j in range(n - 1, -1, -1): # 倒序 while stack and nums[stack[-1]] >= nums[j]: # 这里也是一样的逻辑,stack从下往上递增 stack.pop() if not stack: res[j][1] = -1 else: res[j][1] = stack[-1] stack.append(j) return res
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型vector<vector<>> */ vector<vector<int> > foundMonotoneStack(vector<int>& nums) { // write code here // 定义一个数组 保存左边界的结果 // 思路就是,从左向右开始计算,去计算每个值的左边界,存在记录,不存在就是-1 vector<int> vec1; vec1.push_back(-1); int n = nums.size(); for(int i=1; i<nums.size(); i++) { bool flag = false; for(int j=i-1; j>=0; j--) { if(nums[i] > nums[j]) { vec1.push_back(j); flag = true; break; } } if(!flag) vec1.push_back(-1); } // 定义一个右边界的数组,从右开始往左计算,计算每个值的有边界,存在记录,不存在-1 // 另外顺序是是逆序的,所有需要reverse 其实也可以直接定义一个等大的数组 // 可以节约reverse的时间 vector<int> vec2; vec2.push_back(-1); for(int i=n-2; i>=0; i--) { bool flag = false; for(int j=i+1; j<n; j++) { if(nums[i] > nums[j]) { vec2.push_back(j); flag = true; break; } } if(!flag) vec2.push_back(-1); } reverse(vec2.begin(), vec2.end()); // 重新装成输出的格式 vector<vector<int>> res; for(int i = 0; i<n; i++) { res.push_back({vec1[i], vec2[i]}); } return res; } };
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums intvector * @return intvector<vector<>> */ vector<vector<int> > foundMonotoneStack(vector<int>& nums) { // write code here vector<vector<int>>ans(nums.size(),vector<int>(2)); int stack[1000]={0}; int top = 0; //left ans[0][0] = -1; stack[top++] = 0; for(int i = 1; i < nums.size(); i++) { while(top != 0){ if(nums[i] > nums[stack[top-1]]){ ans[i][0] = stack[top-1]; stack[top++] = i; break; }else{ top--; } } if(top == 0){ stack[top++] = i; ans[i][0] = -1; } } //right ans[nums.size()-1][1] = -1; top=0; stack[top++] = nums.size()-1; for(int i = nums.size()-1; i >= 0; i--) { while(top != 0){ if(nums[i] > nums[stack[top-1]]){ ans[i][1] = stack[top-1]; stack[top++] = i; break; }else{ top--; } } if(top == 0){ stack[top++] = i; ans[i][1] = -1; } } return ans; } };
class Solution: def foundMonotoneStack(self, nums: List[int]) -> List[List[int]]: # write code here res = [] for i in range(len(nums)): l, r = i, i while l >= 0: if nums[i] <= nums[l]: l -= 1 else: break while r < len(nums): if nums[i] <= nums[r]: r += 1 else: break if r == len(nums): r = -1 res.append([l, r]) return res
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int一维数组 * @return int二维数组 */ public int[][] foundMonotoneStack (int[] nums) { // write code here int arr[][]=new int[nums.length][2]; for(int i=0;i<nums.length;i++){ int left=-1; int right=-1; //最左边 if(i==0){ //左 arr[i][0]=-1; //右遍遍历寻找最近比arr[i]小的值 for(int j=i+1;j<arr.length;j++){ if(nums[j]<nums[i]){ right=j; break; } } arr[i][1]=right; } //最右边 if(i==nums.length-1){ //右 arr[i][1]=-1; //左遍历寻找最近比arr[i]小的值 for(int j=i-1;j>=0;j--){ if(nums[j]<nums[i]){ left=j; break; } } arr[i][0]=left; } //中间情况 if(i!=0&&i!=nums.length-1){ //左遍历寻找最近比arr[i]小的值 for(int j=i-1;j>=0;j--){ if(nums[j]<nums[i]){ left=j; break; } } arr[i][0]=left; //右遍历寻找最近比arr[i]小的值 for(int j=i+1;j<nums.length;j++){ if(nums[j]<nums[i]){ right=j; break; } } arr[i][1]=right; } } return arr; } }
单调递增栈。遇到小的通通出栈。
import java.util.*; public class Solution { public int[][] foundMonotoneStack (int[] nums) { List<Integer> leftList = new ArrayList<>(); List<Integer> rightList = new ArrayList<>(); int[][] res = new int[nums.length][2]; for(int i = 0; i < res.length; ++i) { res[i][0] = -1; res[i][1] = -1; } for(int i = 0; i < nums.length; ++i) { while(leftList.size() != 0 && nums[leftList.get(leftList.size() - 1)] > nums[i]) { res[leftList.get(leftList.size() - 1)][1] = i; leftList.remove(leftList.size() - 1); } while(rightList.size() != 0 && nums[rightList.get(rightList.size() - 1)] > nums[nums.length - 1 - i]) { res[rightList.get(rightList.size() - 1)][0] = nums.length - 1 - i; rightList.remove(rightList.size() - 1); } rightList.add(nums.length - 1 - i); leftList.add(i); } return res; } }
package main /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int一维数组 * @return int二维数组 */ func foundMonotoneStack( nums []int ) [][]int { n:=len(nums) ans:=make([][]int,n) for i,_:=range ans{ ans[i]=[]int{-1,-1} } stk1:=[]int{} stk2:=[]int{} for i,j:=0,n-1;i<n&&j>=0;i,j=i+1,j-1{ for len(stk1)>0&&nums[stk1[len(stk1)-1]]>nums[i]{ ans[stk1[len(stk1)-1]][1]=i stk1=stk1[:len(stk1)-1] } stk1=append(stk1,i) for len(stk2)>0&&nums[stk2[len(stk2)-1]]>nums[j]{ ans[stk2[len(stk2)-1]][0]=j stk2=stk2[:len(stk2)-1] } stk2=append(stk2,j) } return ans }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型vector<vector<>> */ vector<vector<int> > foundMonotoneStack(vector<int>& nums) { // write code here vector<vector<int>> res; for(int i = 0;i<nums.size();++i) { int L = -1; int R = -1; int val = nums[i]; for(int j = i-1;j>=0;--j) { if(nums[j]<nums[i]) { L = j; break; } } for(int z = i+1;z < nums.size();++z) { if(nums[z]<nums[i]) { R = z; break; } } res.emplace_back(vector<int>{L,R}); } return res; } };
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @return int整型二维数组 */ public int[][] foundMonotoneStack (int[] nums) { // write code here int[][] res = new int[nums.length][2]; Stack<Integer> stack = new Stack<>(); for(int i = 0; i < nums.length; i++){ while(!stack.isEmpty() && nums[stack.peek()] > nums[i]){ int j = stack.pop(); res[j][1] = i; } if(stack.isEmpty() || nums[stack.peek()] == nums[i]){ res[i][0] = -1; }else{ res[i][0] = stack.peek(); } stack.push(i); } while(!stack.isEmpty()){ res[stack.pop()][1] = -1; } return res; } }
public class Solution { public int[][] foundMonotoneStack (int[] nums) { //由于本体存在重复值,需要使用双向链表存放相同值 Stack<LinkedList<Integer>> stack = new Stack<>(); //存放结果的数组 int result[][] = new int[nums.length][2]; //依次遍历nums中每一个元素,i为数组的下标 for(int i=0;i<nums.length;i++) { //栈本身遵顼从小到大的单调原则,如果出现反例则陆续从栈中弹出元素直到符合原则 //弹出的元素即是需要处理的信息 while(!stack.isEmpty()&&nums[stack.peek().peekLast()]>nums[i]) { //取出栈顶的链表,从尾部开始一次赋值 LinkedList<Integer> tmp = stack.pop(); while(!tmp.isEmpty()) { int index = tmp.pollLast(); //如果弹出元素后栈为空则left值为-1.否则left的值为当前栈顶链表的尾元素的值 //right值为即将进入栈的元素,下标就是i if(stack.isEmpty()) { result[index][0]=-1; result[index][1]=i; } else { result[index][0]=stack.peek().peekLast(); result[index][1]=i; } } } //每遍历一个元素,相当于处理的是之前的元素,处理之后该元素仍需要入栈 //如果该元素的值和当前栈顶元素对应的值相等,则添加到一个链表中,否则创建一个新链表 if(!stack.isEmpty()&&nums[stack.peek().peekLast()]==nums[i]) { stack.peek().addLast(i); } else { LinkedList<Integer> res = new LinkedList<>(); res.addLast(i); stack.add(res); } } //此时所有的元素已经遍历完成,该添加进去的元素已经添加过了 //此时栈里剩下的元素都是符合单调栈原则从小到大排列的 //依次从栈顶弹出元素,right值为-1,left值为弹出后此时栈顶元素的链表尾部的下标 //情况与上面类似,只不过right值为-1,当栈弹空时left为-1 while(!stack.isEmpty()) { LinkedList<Integer> tmp = stack.pop(); while(!tmp.isEmpty()) { int index = tmp.pollLast(); if(stack.isEmpty()) { result[index][0]=-1; result[index][1]=-1; }else { result[index][0]=stack.peek().peekLast(); result[index][1]=-1; } } } return result; } }感觉写的挺清楚的,就是挺繁琐的,耗时有点高
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums intvector * @return intvector<vector<>> */ vector<vector<int> > foundMonotoneStack(vector<int>& nums) { // write code here int top = -1; int n=nums.size(); stack<int> stk; vector<vector<int>> array(n);//定义一个5*2的数组存放结果 for (int i = 0; i < array.size(); i++) array[i].resize(2); for ( int i = 0; i < n; i++ ) { while ( !stk.empty() && nums[stk.top()] >= nums[i] ) stk.pop();//保证栈顶元素是小于待入栈的 if ( stk.empty() ) array[i][0] = -1;//栈为空,说明该位置元素左侧没有比它小的数 else array[i][0] = stk.top();//如果栈不为空,则左侧比其值小的元素位置距离最近 stk.push(i);//该元素入栈 } while(!stk.empty()) stk.pop();//清空栈 for ( int i = n - 1; i >= 0; i-- ) { while (!stk.empty() && nums[stk.top()] >= nums[i] ) stk.pop(); if ( stk.empty() ) array[i][1] = -1;//栈为空,说明该位置元素右侧没有比它小的数 else array[i][1] = stk.top();//如果栈不为空,则右侧比其值小的元素位置距离最近 stk.push(i);//该元素入栈 } return array; } };
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型vector<vector<>> */ vector<vector<int> > foundMonotoneStack(vector<int>& nums) { // write code here int n = nums.size(); vector<int> left(n) , right(n); stack<int> s; for(int i = 0;i < n;i++){ while(!s.empty() && nums[i] <= nums[s.top()]) s.pop(); left[i] = s.empty() ? -1 : s.top(); s.push(i); } s = stack<int> (); for(int i = n - 1;i >= 0;i--){ while(!s.empty() && nums[i] <= nums[s.top()]) s.pop(); right[i] = s.empty() ? - 1 : s.top(); s.push(i); } vector<vector<int>> res; for(int i = 0; i < n;i++) res.push_back({left[i],right[i]}); return res; } };
//单调栈 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums intvector * @return intvector<vector<>> */ vector<vector<int> > foundMonotoneStack(vector<int>& nums) { // write code here stack<int> s; int n = nums.size(); vector<vector<int>> res(n, vector<int>(2,0)); for(int i = 0; i < n; ++i){ while(!s.empty() && nums[s.top()] >= nums[i]) s.pop(); if(s.empty()) res[i][0] = -1; else res[i][0] = s.top(); s.push(i); } while(!s.empty()) s.pop(); for(int i = n-1; i >= 0; --i){ while(!s.empty() && nums[s.top()] >= nums[i]) s.pop(); if(s.empty()) res[i][1] = -1; else res[i][1] = s.top(); s.push(i); } return res; } };
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int一维数组 * @return int二维数组 */ public int[][] foundMonotoneStack (int[] nums) { // write code here Stack<Integer> stack = new Stack<>(); int[][] result = new int[nums.length][2]; stack.push(-1); for(int i=0; i<nums.length; i++) { while(stack.peek()!=-1 && nums[stack.peek()]>nums[i]) { //因为比较的数字一定比栈顶元素小,所以这里可以设定每个栈顶元素的右边较小数 result[stack.peek()][1] = i; stack.pop(); } //上面while循环中条件必须是>,不能是>=,因为等于的情况不能把结果加入结果集,需要单独提出来讨论 //(如果与栈顶元素相等说明自己左边的最近较小数与栈顶元素左边较小数一样,如果不相等说明栈顶元素就是左边的最近较小数)。 if(stack.peek()!=-1 && nums[stack.peek()]==nums[i]) { result[i][0] = result[stack.peek()][0]; }else { result[i][0] = stack.peek(); } stack.push(i); } //stack中剩余的说明这些数字右边都没有比自己小的数字(因为是单调递增栈),那么把他们的结果集里第二个数字设为-1 while(stack.peek()!=-1){ result[stack.pop()][1] = -1; } return result; } }
public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int一维数组 * @return int二维数组 */ public int[][] foundMonotoneStack (int[] nums) { Deque<Integer> stack = new LinkedList<>(); stack.push(-1); int len = nums.length; int[][] res = new int[len][2]; for(int i = 0; i < len; i++){ while (stack.peek() != -1 && nums[stack.peek()] >= nums[i]){ stack.poll(); } res[i][0] = stack.peek(); stack.push(i); } stack.clear(); stack.push(-1); for(int i = len - 1; i >= 0; i--){ while (stack.peek() != -1 && nums[stack.peek()] >= nums[i]){ stack.poll(); } res[i][1] = stack.peek(); stack.push(i); } return res; } }