HackerRank有毒植物问题：栈解法部分测试用例失败求助

问题描述 #

HackerRank Stack板块的有毒植物问题：花园里的植物都喷洒了农药，每天若某植物农药量大于左侧植物则会死亡，求植物不再死亡的天数。约束：植物数量1≤n≤100000，农药量0≤p[i]≤1000000000。示例：p=[3,6,2,7,5]，第1天植物2、4死亡，剩余[3,2,5]；第2天植物3死亡，剩余[3,2]，此时无植物死亡，共2天。

你的代码与问题 #

你尝试用栈实现解法，多数测试用例通过，但31个用例中有4个失败（例如某2429个植物的测试用例，预期输出16，实际输出10）。代码如下：

public static int poisonousPlants(List<Long> p) {
    Stack<Long> st = new Stack<>();
    int count = 0;
    int max = 0;
    for(int i = p.size()-1; i >= 0; i--){
        while(!st.isEmpty() && p.get(i) < st.peek()){
            st.pop();
            count++;
            max = Math.max(max, count);
        }
        if(st.isEmpty() || p.get(i) >= st.peek()){
            st.push(p.get(i));
            count = 0;
        }
    }
    return max;
}

你的思路是反向遍历数组，若当前元素大于等于栈顶则入栈；若小于栈顶则弹出栈顶并计数，更新最大天数。但这个逻辑存在核心错误。

错误原因分析 #

你的思路最大问题是将连续弹出的次数直接等同于死亡天数，但植物的死亡是按天递进的，并非所有被当前元素"压制"的植物都会在同一天死亡。

举个直观的反例：数组[1,5,4,3,2]，按题目规则：

• 第1天：5>1，死亡，剩余[1,4,3,2]
• 第2天：4>1，死亡，剩余[1,3,2]
• 第3天：3>1，死亡，剩余[1,2]
• 第4天：2>1，死亡，剩余[1]
  总天数应为4天，但你的代码反向遍历后会返回max=1，完全不符合预期。

这是因为反向遍历的弹出操作混淆了植物死亡的时间顺序：右侧的植物先死亡，左侧的后死亡，天数是累加的，而非一次性计数。你的代码把所有弹出的植物都算成同一天死亡，自然会得到错误结果。

正确的栈解法 #

正确的思路是正向遍历数组，栈中存储的不仅是植物的农药量，还要记录该植物的死亡天数（即它需要多少天会死亡）。通过跟踪每个植物的死亡时间，取最大值得到最终结果。

代码实现（自定义类版） #

import java.util.Stack;
import java.util.List;

class Plant {
    long pesticide;
    int days;
    Plant(long p, int d) {
        pesticide = p;
        days = d;
    }
}

public static int poisonousPlants(List<Long> p) {
    Stack<Plant> stack = new Stack<>();
    int maxDays = 0;
    for (int i = 0; i < p.size(); i++) {
        int currentDays = 0;
        // 弹出所有比当前植物农药量小的元素，这些植物会先死亡
        while (!stack.isEmpty() && stack.peek().pesticide < p.get(i)) {
            currentDays = Math.max(currentDays, stack.peek().days);
            stack.pop();
        }
        // 若左侧存在更大的植物，当前植物会在currentDays+1天死亡；否则不会死亡
        if (!stack.isEmpty()) {
            currentDays = p.get(i) > stack.peek().pesticide ? currentDays + 1 : 0;
        } else {
            currentDays = 0;
        }
        maxDays = Math.max(maxDays, currentDays);
        stack.push(new Plant(p.get(i), currentDays));
    }
    return maxDays;
}

代码实现（双栈版） #

如果不想自定义类，可以用两个栈分别存储农药量和对应的死亡天数：

import java.util.Stack;
import java.util.List;

public static int poisonousPlants(List<Long> p) {
    Stack<Long> pesticideStack = new Stack<>();
    Stack<Integer> daysStack = new Stack<>();
    int maxDays = 0;
    for (long num : p) {
        int currentDays = 0;
        while (!pesticideStack.isEmpty() && pesticideStack.peek() < num) {
            currentDays = Math.max(currentDays, daysStack.pop());
            pesticideStack.pop();
        }
        if (!pesticideStack.isEmpty()) {
            currentDays = num > pesticideStack.peek() ? currentDays + 1 : 0;
        } else {
            currentDays = 0;
        }
        maxDays = Math.max(maxDays, currentDays);
        pesticideStack.push(num);
        daysStack.push(currentDays);
    }
    return maxDays;
}

逻辑说明 #

1. 正向遍历每个植物，对于当前植物，先弹出栈中所有农药量比它小的元素：这些植物会在当前植物之前死亡，因此当前植物的死亡天数需要参考这些植物的最长存活天数。
2. 如果栈不为空，说明当前植物左侧存在更大的植物：若当前植物农药量更大，则它会在之前统计的天数+1天死亡；否则不会死亡。
3. 记录所有植物的死亡天数，取最大值即为最终答案。

内容的提问来源于stack exchange，提问作者user7324674