Curs 9. Stiva 1. Parantezare & Skyline

#include <stack>
using namespace std;

stack<int>st;


int main() {
  st.push(3);
  cout << st.top(); // 3
  
  st.push(5);
  st.push(7);
  st.pop();
  cout << st.top();//5
  
  push
  pop
  push
  pop
  push
  pop
  10000
  
  
}

int st[10001];
int cnt = 0;

int main() {
  st[++cnt] = 1;
  st[++cnt]= 3;
  
  cout << st[cnt] // 3;
  --cnt; /pop;
  
  cout << st[cnt] // 1;
  
  
}


st.push(3);
st.push(5);
st.pop();
st.push(7);


7 top()
3

Parantezare

(())
)(()
((()())())
()(

1. Numarul de paranteze ( = nr de paranteze )  )(()
2. Incepe cu paranteza ( si se termina cu paranteza ) => ( ) )( ()

STIVA:
()(


#include <stack>
using namespace std;

4
(())
)(()
((()())())
()(
int main() {
cin >> n;
for(int i = 1;i<= n; ++i) {
char t[260];
cin >> t; // separa dupa spatii si randuri noi // citire pe cuvinte
stack<char>st;
bool ok = true;
for(int j = 0; j < strlen(t); ++j){ 
      if(t[j] == '(') {
        st.push(t[j]); 
        ma = max(ma, st.size());
        }
          if(t[j] == '[') {
        st.push(t[j]); 
        ma = max(ma, st.size());
        }
      else if(t[j]==')'{
        if(!st.empty() && st.top() == '(')
            st.pop();
       else   {
          ok = false;
           break;   
           }
        }
        }
      else if(t[j]==']'){
        if(!st.empty() && st.top() == '[')
            st.pop();
       else   {
          ok = false;
           break;   
           }
        }
        }
      
  }
  if(ok == true && st.empty())
    cout << 1 << "\n";
  else
    cout <<0 << "\n";
}
}

5
3 4 3 5 1

int v[10001];
int main() {
cin >> n;
for(int i = 1;i <=n;++i)
  cin >> v[i];
  
for(int i = 1; i <= n; ++i)  {
ok = false;
  for(int j = i+1; j <= n; ++j)
    if(v[j] > v[i]) {
      cout<< v[j] << " ";
      ok = true;
      break;
      }
  if(ok == false)
    cout <<-1 << " ";
}
}
O(N^2) 

5           
         i
3 4 3 5 1 

 4 5 5  -1 -1
STIVA:

4
5
Skyline
int sol[100001];
cin >> n;
for(int i = 1;i <=n;++i)
  cin >> v[i];
sol[n] = -1;
st.push(v[n]);
for(int i = n-1; i >= 1; --i) {
  while(!st.empty() && v[i] > st.top()) {
    st.pop();
  }
  if(st.empty())
    sol[i]=-1;
  else
    sol[i] = st.top();
  
  st.push(v[i]);
}
N intrari in stiva N iesi din stiva => O(N);


3 4 2 5 3
-1 3 -1 2 2
-1 -1 4 -1 5


int sol_st[100001];
cin >> n;
for(int i = 1;i <=n;++i)
  cin >> v[i];

 cin >> Q;
 char directie;
 int pozitie;
 for(int i = 1;i <=Q; ++i ){
 cin >> directie >> poz;
   if(directie == 'D')
     cout << sol_dr[poz];
   else
     cout << sol_st[poz];
 } 
}sol_st[1] = -1;
st.push(v[1]);
for(int i = 1; i <= N; ++i) {
  while(!st.empty() && v[i] < st.top()) {
    st.pop();
  }
  if(st.empty())
    sol_st[i]=0;
  else
    sol_st[i] = st.top();
  
  st.push(v[i]);
  }
  
  while(!st.empty())
    st.pop();
sol_dr[n] = -1;
st.push(v[n]);
for(int i = n-1; i >=1; --i) {
  while(!st.empty() && v[i] < st.top()) {
    st.pop();
  }
  if(st.empty())
    sol_dr[i]=0;
  else
    sol_dr[i] = st.top();
  
  st.push(v[i]);
 

cin >> n;
for(int i = 1;i <= n; ++i) {
  cin >> inaltime[i] >> lungime[i];
}
for(int i = 1; i <= n; ++i)
  sp_lung[i] = sp_lung[i-1] + v[i];
sol_st[1] = -1;
st.push(inaltime[1]);
for(int i = 1; i <= N; ++i) {
  while(!st.empty() && inaltime[i] < st.top()) {
    st.pop();
  }
  if(st.empty())
    sol_st[i]=0;
  else
    sol_st[i] = st.top();
  
  st.push(v[i]);
  }
  
  while(!st.empty())
    st.pop();
sol_dr[n] = -1;
st.push(inaltime[n]);
for(int i = n-1; i >=1; --i) {
  while(!st.empty() && inaltime[i] < st.top()) {
    st.pop();
  }
  if(st.empty())
    sol_dr[i]=0;
  else
    sol_dr[i] = st.top();
  
  st.push(v[i]);
 }

for(int i = 1; i <=n; ++i) {
  //CLADIREA I este coloana dreptunghiului
  //COLOANA = dreptunghiul contine cladirea I si are inaltimea ei
  //Dreptunghiul este de la sol_st[i]+1 .... sol_dr[i]-1 cu inaltimea inaltime[i]; 
  //Daca sol_st[i] = - 1 => 1
  //Daca sol_dr[i] =-1 => n
  if(sol_st[i] ==-1)
    st = 1;
  else
    st = sol_st[i] + 1;
  if(sol_dr[i] ==-1)
    dr = n;
  else
    dr = sol_dr[i] -1;
  aria = inaltime[i] * (sp_lung[dr] - sp_lung[st-1]);
  ma = max(ma, aria);
}
cout << ma;


O(N)

3 5  2 6 

6
2


UN ALGORITHM NOU: SKYLINE
Calculeaza urmatorul element din dreata/stanga mai mare sau mai mic

stack
sol_st
sol_dr
......
for(int i = 1; i <=n ; ++i) {

}


https://www.infoarena.ro/problema/evaluare