962. Maximum Width Ramp

问题:

给定数组,求一对 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 };

 

上一篇:CF1092F Tree with Maximum Cost(换根dp)


下一篇:718. Maximum Length of Repeated Subarray