问题:
给定数组,求一对 index为 ( i , j ) 的 A[i] <= A[j] && i < j,两个index距离最远。(即max(j-i))
Example 1: Input: [6,0,8,2,1,5] Output: 4 Explanation: The maximum width ramp is achieved at (i, j) = (1, 5): A[1] = 0 and A[5] = 5. Example 2: Input: [9,8,1,0,1,9,4,0,4,1] Output: 7 Explanation: The maximum width ramp is achieved at (i, j) = (2, 9): A[2] = 1 and A[9] = 1. Note: 2 <= A.length <= 50000 0 <= A[i] <= 50000
解法1:
使用排序的map去存储,元素数值 与 index数组信息 {A[i], array[...]}。
(同一个数值可能有多个,在不同位置)
array[0]为该数值A[i]的最小index,array[end]为该数值A[i]的最大index
(令end=array.size()-1)
遍历构建好的map
由于已经根据元素值排序过,
依次记录最小的index值。lowestindex = min(lowestindex, array[0]);
和当前值的最大index值的差:res = max(res, array[end]-lowestindex);
这样对每个数值,都进行了res求解。从中选出最大差值,即为要求结果。
代码参考:
1 class Solution { 2 public: 3 int maxWidthRamp(vector<int>& A) { 4 map<int, vector<int>> pos; 5 int res=0; 6 int lowestindex=A.size(); 7 for(int i=0; i<A.size(); i++){ 8 pos[A[i]].push_back(i); 9 } 10 for(auto p:pos){ 11 int end=p.second.size()-1; 12 lowestindex = min(lowestindex, p.second[0]); 13 res=max(res, p.second[end]-lowestindex); 14 } 15 return res; 16 } 17 };
解法2:
1.构建decreasing stack
记录 ( i , j ) 中的 i:尽量左边,尽量最小
比如对一个数组[3,28,15,1,4,0]
我们选取 i 的话,从第一个元素 3 开始选取,
[3]
接着选取下一个 28 时,发现,如果以28为 i,任何满足条件的 j (>=28) 都是满足前一个元素 3 的,
要尽量选择左边的 i 的话,相对于(28, j)我们宁愿选择(3, j),因为其距离差值选择3更大。因此我们不选择28
接着选取下一个 15 同上,
接着选取下一个 1 时,满足条件的 j 如果=2的时候,即不能向上面那样,选择3去替代1的情况。因此我们需要选入1
[3,1]
...
同理,我们最终得到的即是一个递减栈[3,1,0]
2.从最右边开始遍历j:尽量右边,尽量最大
一直遍历到 j>res即可
理由是:如果j已经小于等于res了,那么j-i就更小于等于res了,res要求最大,就不必去尝试了。
对于每一个j,我们去比较栈顶元素。
如果满足条件,A[s.top] <= A[j],那么构建栈已经保证i=s.top为i的最左边。j也是最右边,那么当前的j-i可作为备选答案,选入res中。
res=max(res, s.top-j);
接着,pop栈顶,我们再判断下一个栈顶元素,如果满足条件,同上。
如果不满足条件:我们需要判断下一个j-1,按理说,应该重新用最初的栈,开始重新判断。
但是,由以下理由,我们不需要再重新恢复栈,重新判断:
首先,到上一个满足条件的res为止,res已经取得最大,即为j-s.top的距离,
那么小于这个距离的,我们不必再去判断。j-1后,使得 i 从s.top-1开始向左判断(与A[j-1]的关系)。
我们直接pop,直接选择新的s.top(省略了 新s.top+1 ~ 原s.top-1)来判断的理由:
如果存在某个值A[k]<A[j-1]满足题意的话,(k在【原来的top-1的位置】->【现在的top】之间)
由于A[k]一定 >= 现在的A[top] (stack是递减的),
那么现在的A[top]<=A[k]<A[j-1]也满足题意。
那还不如去选择 现在的A[top],因为top更靠左。
因此直接去尝试现在的A[top],
如果不满足,那么(从原来的top-1的位置->现在的top)都不会满足<A[j-1]
代码参考:
1 class Solution { 2 public: 3 int maxWidthRamp(vector<int>& A) { 4 int res=0; 5 // 构建decreasing stack记录(i,j)中的 i:尽量左边,尽量最小 6 stack<int> s; 7 for(int i=0; i<A.size(); i++){ 8 if(s.empty() || A[i] < A[s.top()]){ 9 s.push(i); 10 } 11 } 12 //从最右边开始遍历j:尽量右边,尽量最大 13 for(int j=A.size()-1; j>res; j--){ 14 //如果j已经小于等于res了,那么j-i就更小于等于res了,res要求最大,就不必去尝试了。 15 while(!s.empty() && A[s.top()]<=A[j]){//满足题意:A[i]<=A[j] 16 res=max(res, j-s.top()); 17 s.pop(); 18 //pop的理由:pop后的top不满足题意:top>A[j] 19 //那么尝试A[j-1]这个元素: 20 //对于原来的top:这时的(j-1)-i一定<刚才的j,因此不考虑原来的top 21 //(从原来的top-1的位置->现在的top),逐次考虑:与A[j-1]的关系 22 //如果存在某个值A[k]<A[j-1]满足题意的话, 23 //(k在【原来的top-1的位置】->【现在的top】之间) 24 //由于A[k]一定 >= 现在的A[top] (stack是递减的), 25 //那么现在的A[top]<=A[k]<A[j-1]也满足题意。 26 //那还不如去选择 现在的A[top],因为top更靠左。 27 //因此直接去尝试现在的A[top], 28 //如果不满足,那么(从原来的top-1的位置->现在的top)都不会满足<A[j-1] 29 } 30 } 31 return res; 32 } 33 };