立即输出错误以前较大的数字代码

Question

阙：N数字作为输入传递给程序。该程序必须打印前一个较大的数字。如果对于该特定号码没有这样的较大数字打印0。

注意：由于N可以高达100000，所以优化您的算法以避免超时。

输入格式：第一行包含N.第二行包含用空格分隔的N个数字。

输出格式：第一行包含N个数字，表示前一个较大的数字。

边界条件：2 < = N < = 100000

实施例输入/输出1：输入：11 455 346 76 304 488 374 385 433 350 9 1000

输出：0 455 346 346 0 488 488 488 433 350 0

我的代码如下：我的代码

#include <iostream> 

using namespace std; 

int main(int argc, char** argv) 
{ 
int n; 
int a[100000],b[100000]; 
cin>>n; 
for(int i=0;i<n;i++) 
{ 
    cin>>a[i]; 
} 

for(int i=1;i<n;i++) 
{ 
    if(a[i]>a[i-1]) 
    { 
     b[i]=0; 
    } 
    else 
    { 
     b[i]=a[i-1]; 
    } 
} 

b[0]=0; 

for(int i=0;i<n;i++) 
{ 
    cout<<b[i]<<" "; 
} 
} 

输出：0 455 346 0 0 488 0 0 433 350 0

预计：0 455 346 346 0 488 488 488 433 350 0

我这里无法弄清楚这个问题，请建议如何优化代码。

Answer 1

的方法 -

1. 使用栈将跟踪升序以前更大的元素。

2. 不要从左到右扫描和每一个元素arr[i]，保持从堆栈弹出，直到堆栈的顶部元素大于当前数量

   我。如果堆栈为空，则没有比当前更多的数字。打印0

   ii。否则打印堆栈的最上面的元素，它是前一个更大的数字。

3. 将当前元素推入堆栈。

代码：

void immediatePreviousLarger(int arr[], int n) { 
    stack<int> Stack; 
    for(int i = 0; i < n; i++) { 
     while(!Stack.empty() and Stack.top() <= arr[i]) { 
      Stack.pop(); 
     } 
     if(Stack.empty()) { 
      printf("0 "); 
     } else { 
      printf("%d ", Stack.top()); 
     } 
     Stack.push(arr[i]); 
    } 
} 

时间复杂度O(n)。