Poisonous Plants

I have solved the following problem. My code works but Hackerrank says that I can do faster:


There are plants in a garden. Each of these plants has been added
with some amount of pesticide. After each day, if any plant has more
pesticide than the plant at its left, being weaker than the left one,
it dies. You are given the initial values of the pesticide in each
plant. Print the number of days after which no plant dies, i.e. the
time after which there are no plants with more pesticide content than
the plant to their left.


Input Format


The input consists of an integer . The next line consists of integers
describing the array where denotes the amount of pesticide in plant
.


Constraints


\$1 \leq N \leq 100000\$


\$0 \leq P[i] \leq 10^9\$


Output Format


Output a single value equal to the number of days after which no
plants die.


Sample Input

7  
6 5 8 4 7 10 9

Sample Output

2

My code:

```
import java.io.*;
import java.util.*;

public class Solution {
static Stack aStack = new Stack();
static Stack bStack = new Stack();

static int printDays(Stack aStack){
int objectsRemoved=-1;
int countLoops=0;

while(objectsRemoved!=0) {

objectsRemoved=0;

int prevValue=0;
int curValue=0;

while(!aStack.isEmpty()) {

curValue = (int)aStack.pop();

if(!aStack.isEmpty()){
int tempValue = (int)aStack.pop();
if(curValue<=tempValue){
bStack.push(curValue);
}
else{
objectsRemoved++;
//System.out.println("Removed " + curValue);
}
aStack.push(tempValue);
}
else{
bStack.push(curValue);

While I suspect there is better than O(daysN) algorithm available, my idea was looking fairly complex for non-trivial inputs, probably not worth it as long as single array modification can do the brute force simulation. Although I'm not sure about Java's performance of arrays, but in C/C++ this would be flying and any more clever algorithm would have to be really $#%$#^& clever to beat 100k int array manipulation (even when we are talking 100k100k in worst case, that's still only 10bil operations.. while the clever algo would solve it with O(100k), but that's quite special case).

So I wonder, whether you get "make it faster" because of algorithm, or because of your coding technique.

Your brute force days simulation can be written like this:

(edit: version two with slight initial search optimization)

static int simulateDays(final int[] plants){
    if (plants.length <= 1) return 0;
    int plantSize = plants.length, days = 0, i, lastDying = 1;
    while (true) {      // simulate as many days as needed
        // Search for first plant to die today
        for (i = lastDying; i < plantSize; ++i) {
            if (plants[i-1] < plants[i]) break;
        }
        if (i == plantSize) return days;  // no plant found to be dying
        lastDying = i;      // optimize the initial search next day
        int removed = 1;    // the one found (plants[i]) will die
        // Now search remaining plants for any other dying today and also remove all of them
        for (++i; i < plantSize; ++i) {
            if (plants[i-1] < plants[i]) {  // plant[i] dies, count+skip it.
                ++removed;
            } else {                        // plant[i] survives, move it to last living one
                plants[i-removed] = plants[i];
            }
        }
        plantSize -= removed;               // adjust total number of remaining plants
        ++days;                             // let's see another day
    }
}

Should be faster, as it doesn't use complex container Stack, only single int[] array, and no dynamic allocations, the whole simulation is contained in original array... but I didn't profile it, as the sample inputs I have are too small to do that.

I only tested it works for the sample case you posted, and few others I tried (to verify correctness of it).

I'm curious, if this change is enough to get better rating, let me know please. :)

edit:
The worst input case for this approach is of course something like 100k of plants: 5 6 6 6 6 6 ... (so all the "6" plants will die after meeting with "5", each day only one, causing whole rest of array to move by one to left).

StackExchange Code Review Q#133486, answer score: 6