FilesExpand file tree

 master

/

ansv.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

28 lines (27 loc) · 1015 Bytes

 master

/

ansv.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

28 lines (27 loc) · 1015 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

// Linear time all nearest smaller values, standard stack-based algorithm.

// ansv_left stores indices of nearest smaller values to the left in res. -1 means no smaller value was found.

// ansv_right likewise looks to the right. v.size() means no smaller value was found.

void ansv_left(vector<int>& v, vector<int>& res) {

stack<pair<int, int> > stk; stk.push(make_pair(INT_MIN, v.size()));

for (int i = v.size()-1; i >= 0; i--) {

while (stk.top().first > v[i]) {

res[stk.top().second] = i; stk.pop();

}

stk.push(make_pair(v[i], i));

}

while (stk.top().second < v.size()) {

res[stk.top().second] = -1; stk.pop();

}

}

void ansv_right(vector<int>& v, vector<int>& res) {

stack<pair<int, int> > stk; stk.push(make_pair(INT_MIN, -1));

for (int i = 0; i < v.size(); i++) {

while (stk.top().first > v[i]) {

res[stk.top().second] = i; stk.pop();

}

stk.push(make_pair(v[i], i));

}

while (stk.top().second > -1) {

res[stk.top().second] = v.size(); stk.pop();

}

}