fork(1) download 
  1. #include <iostream>
  2. #include <stack>
  3. using namespace std;
  4.  
  5. void test()
  6. {
  7. 	int Arr[] = {5,7,9,2,8,11,16,10,12};
  8. 	int Sol[9];
  9.  
  10. 	stack<int> undecided;   // or a stack implemented using a linked list
  11.  
  12. 	Sol[0] = -1;    // this is a given
  13.  
  14. 	for(int i = 9 - 1; i != 0; --i) {
  15. 	    undecided.push(i); // we haven't found a smaller value for this Arr[i] item yet
  16. 	                       // note that all the items already on the stack (if any)
  17. 	                       // are smaller than the value of Arr[i] or they would have
  18. 	                       // been popped off in a previous iteration of the loop
  19. 	                       // below
  20.  
  21. 	    while (!undecided.empty() && (Arr[i-1] < Arr[undecided.top()])) {
  22. 	        // the value for the item on the undecided stack is
  23. 	        //  larger than Arr[i-1], so that's the index for 
  24. 	        //  the item on the undecided stack
  25. 	        Sol[undecided.top()] = i-1;
  26. 	        undecided.pop();
  27. 	    }
  28. 	}
  29.  
  30. 	// We've filled in Sol[] for all the items have lesser values to
  31. 	//  the left of them.  Whatever is still on the undecided stack
  32. 	//  needs to be set to -1 in Sol
  33.  
  34. 	while (!undecided.empty()) {
  35. 	    Sol[undecided.top()] = -1;
  36. 	    undecided.pop();
  37. 	}
  38.  
  39. 	for (int i = 0; i < 9; ++i) {
  40. 		cout << Sol[i] << ", ";
  41. 	}
  42.  
  43. 	cout << "\n";
  44. }
  45.  
  46.  
  47. int main() {
  48. 	test();
  49. 	return 0;
  50. }
Success #stdin #stdout 0s 4260KB
comments (?)
stdin 
Standard input is empty
stdout 
-1, 0, 1, -1, 3, 4, 5, 4, 7,
https://ideone.com/VXC0yq
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!