昨晚58同城的编程题关于打印前面比当前值小且下标最大？

从后往前，维持一个递减的单调栈，每次元素出栈，该位置该打印的值也就确定了，时间复杂度O(n)

谢谢各位大神的出谋划策，尤其是@特仑苏先生 ，下面我给出代码： import java.util.Stack; public class BiWoXiaoZuiJin { public static int[] findArray(int[] array) { int[] res = new int[array.length]; Stack<Integer> inc = new Stack<>(); for(int i=0; i<array.length; i++) { while(!inc.isEmpty()) { if(inc.peek() >= array[i]) { inc.pop(); } else { res[i] = inc.peek(); inc.push(array[i]); break; } } if(inc.isEmpty()) { inc.push(array[i]); res[i] = -1; } } return res; } public static void main(String[] args) { int[] arr = {3,6,1,4,2,3,7,5,8}; int[] res = findArray(arr); for(int i=0; i<res.length; i++) { System.out.print(res[i] +" "); } } }

数组a为[3,6,1,4,2,3,7,5,8], 则打印[-1,3,-1,1,1,2,3,3,5]。单调栈：array = [] array必须从小到大有序保存结果：res = []1.3入栈 array = [3] res[0] = -12.6入栈 array = [3,6] res[1] = 33.1入栈 3，6出栈 array = [1], res[2]= -14.4入栈 array = [1,4], res[3] = 15.2入栈 4出栈 array = [1,2], res[4] = 16.3入栈 array = [1,2,3] res[5] = 27.7入栈 array = [1,2,3,7] res[6] = 38.5入栈 7出栈 array = [1,2,3,5] res[7] = 39.8入栈 array = [1,2,3,5,8] res[8] = 5res = [-1, 3, -1, 1, 1, 2, 3, 3, 5]

我的思路从后往前遍历，i,j下标，i--，j先标到最后一个。如果值i小于值j，i和j之间的全部设为值j，将i赋给j。如果i等于0时j不等于0，将j处值设为-1，把j赋给i，j--，i--。手机打好麻烦。。。

import java.util.Scanner; //58题    我考虑在遍历每一个数的时候把前面最小值标记出来，如果现在遍历的数比标记的最小值还是小，那就直接输出-1，这样只有在前面存在比当前数小的情况下才会逆向遍历前面的数 public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int arr[] = new int[n]; int brr[] = new int[n]; for (int i = 0; i < arr.length; i++) { arr[i] = sc.nextInt(); } brr[0] = -1; int min=arr[0]; for (int i = 1; i < arr.length; i++) { if(arr[i]<arr[i-1]){ min=arr[i]; } if(arr[i]<min){ brr[i] = -1; continue; } for (int j = i; j >= 0; j--) { if (arr[i] > arr[j]) { brr[i] = arr[j]; break; } else { brr[i] = -1; } } } for (int i = 0; i < brr.length; i++) { System.out.print(brr[i] + " "); } } }

单调栈，楼上已经说了，左神的算法课也讲了，时间复杂度为O(n)

用一个栈  O(n)即可解决  找到进栈出栈的规律 自己试一试   左神讲过这个题

单调栈

看看大神

#include<iostream> #include<vector> #include<iterator> #include<algorithm> using namespace std; void Fun(vector<int> &vec) { int len=vec.size(); for(int i=len-1;i>0;--i) { if(vec[i]>vec[i-1]) { int tmp=vec[i]-vec[i-1]; for(int j=i;j>=0;--j) { int s=vec[i]-vec[j]; if(tmp<s) { tmp=s; } } vec[i]=tmp; } else { vec[i]=-1; } } vec[0]=-1; } int main() { vector<int> vec; int n; cin>>n; for(int i=0;i<n;++i) { int tmp; cin>>tmp; vec.push_back(tmp); } Fun(vec); copy(vec.begin(),vec.end(),ostream_iterator<int>(cout," ")); return 0; }

设两个游标min和max，分别指向当前位置之前最小和最大的数，然后再判断进行打印

我能想到的就是从后往前遍历，最好的时间复杂度是O(n),最坏的是O(n^2),不太稳定。