Блог пользователя Matrix.code

Longest Sub-array with smaller elements

Автор Matrix.code, 10 лет назад, По-английски 
An array of integer is given.. 
For each element of i th index , I need to find the length of the longest sub-array starting from i+1 index where all the element is smaller than arr[i]

Sample : arr[]={10 , 2 , 7 , 4 , 12 ,2 }

for i = 0 , arr[0] = 10 , the sub-array is = {2,7,4} . All are smaller than 10 and starting from 
i + 1 th index ... 
and for i = 1 , length = 0
This need to be done for all the index of the array 

How to find the length ??
Constrains: 
Size of The array = 10^6

I think RMQ will prove necessary here
  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 3   Проголосовать: нравится +18 Проголосовать: не нравится 
stack< pair<int, int> > st;
for (int i = (int)a.size() - 1; i >= 0; --i)
{
    while (!st.empty() && st.top().first < a[i])
        st.pop();
    if (st.empty())
        ans[i] = a.size();
    else
        ans[i] = st.top().second;
    st.push(pair<int, int>(a[i], i));
}
→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Let v be the given array. Initially, you should push to a stack all the elements of v that you have processed. But the main idea is that the stack should have the following invariant: for every element k in the stack, the element k-1 (right below it, if it exists) should necessarily be strictly greater in value than it. Let len_i be the longest sub-array starting from i+1. This way you can be sure that the elements v[i] and v[i+1+len_i] (first element that is not in the sub-array) will never be in the stack at the same time.

So before you push an element v[x] to the stack, you have to pop all the elements from the top of the stack which are lesser or equals in value to the element v[x]. Let v[j], j < x, be an element that was popped from the stack at this step. You can notice that v[x] is the first element which is not in the longest subarray starting from j+1, so you can easily get the longest subarray starting from j+1 by subtracting the positions x and j+1.

// ii is pair<int, int>
// c is the answer array
v.push_back(INFINITE);
stack<ii> s;
for(int x = 0; x < v.size(); x++){
	while(!s.empty() && s.top().first <= v[x]){
		int j = s.top().second; s.pop();
		c[j] = x - (j+1);
	}
	s.push(ii(v[x], x));
}

So we have stack<ii> containing the element value and its position in the original array. You may simplify it by not using pairs, but I think it's ok. You can easily make sure that all the elements were popped from the stack by pushing an INFINITE element to the vector v and looping through all the elements. It's O(n) complexity since the elements are pushed once and popped once.

→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

This is basically just an application of the All nearest smaller values problem, though in our case the situation is kind of reversed. The stack based solution is easier to understand, but I like the following solution more since the code is shorter and it's more memory efficient...

Input: A[0..len)
Output: B[0..len), B[i] contains the index of the first element to the right larger than A[i] (or len if no such element exists).

for(int i = len-1; i>=0; i--)
{
    int j = i+1;
    while(j<len && A[j]<=A[i]) j = B[j];
    B[i] = j;
}

And yeah the complexity is O(n).

→ Ответить