I have been working on Bad Hair Day - POJ 3250 - Virtual Judge. I am using a vector, named “height” to store inputs and a for loop to push elements into a monotonic stack. This way, I can find the next greatest element in linear time. For some reason, the for loop isn’t working and only loops through part of the vector.
> #include <iostream>
> #include <algorithm>
> #include <vector>
> #include <stack>
> #include <map>
>
> using namespace std;
>
> int main () {
> int n;
> cin >> n;
> vector<int> height;
> map<int, int> nextGreatest;
> for (int i = 0; i < n; ++i) {
> int x;
> cin >> x;
> height.push_back(x);
> }
> stack<int> mono_stack;
> cout << "Size of height vector: " << height.size() << std::endl;
> for (int i = 0; i < height.size(); ++i) { // ***Loop through height vector***
> int x = height.at(i);
> cout << i << std::endl; // only prints indices 0-4 in sample test case, where the vector has size of 6
> if (mono_stack.empty()) {
> mono_stack.push(x);
> } else {
> if (mono_stack.top() > x) {
> mono_stack.push(x);
> } else {
> while (mono_stack.top() < x) {
> nextGreatest[mono_stack.top()] = i;
> mono_stack.pop();
> }
> }
> }
> }
> int cnt = 0;
> for (int i = 0; i < n; ++i) {
> int index = nextGreatest[height.at(i)];
> cnt+=(index-i-1);
> }
> cout << cnt;
> return 0;
>
> }
So far, I have been trying to debug the sample test case, and I have placed couts to print the index of the element of the vector that the loop is on. When I run the program, it only prints indices 0 to 4, not 0 to 5 even though the code knows that the vector has size 6.
Also, the debugger says my code has XCS Bad Access Exception with std::map. I’m not returning any value from the map in a function, so how is this happening and why is the for loop not working?
Thank you!