这是关于LintCode 3866 “有效子数组的数量”的问题。这是一个典型的单调栈应用问题，需要计算数组中所有满足特定条件的子数组数量。

问题理解

有效子数组的定义：

• 对于数组 nums 中的某个子数组 nums[i..j]（i ≤ j），如果该子数组的第一个元素 nums[i] 是子数组中的最小值，则称该子数组为有效子数组。

换句话说，对于每个起始位置 i，我们需要找到以 i 为起点，且 nums[i] 是其中最小值的所有子数组。

解题思路

核心思想

对于每个位置 i，我们需要找到第一个小于 nums[i] 的元素位置，记作 nextSmaller[i]。那么：

• 以 i 为起点的有效子数组可以一直延伸到 nextSmaller[i] - 1
• 以 i 为起点的有效子数组数量 = nextSmaller[i] - i

为什么？

• 因为一旦遇到一个比 nums[i] 更小的元素，nums[i] 就不再是子数组的最小值
• 所以所有从 i 开始，结束位置在 [i, nextSmaller[i]-1] 范围内的子数组都满足条件

示例

nums = [1, 4, 2, 5, 3]
nextSmaller: [5, 2, 5, 4, 5] (5表示到达数组末尾)
计算：
i=0: 5-0 = 5 个子数组: [1], [1,4], [1,4,2], [1,4,2,5], [1,4,2,5,3]
i=1: 2-1 = 1 个子数组: [4]
i=2: 5-2 = 3 个子数组: [2], [2,5], [2,5,3]
i=3: 4-3 = 1 个子数组: [5]
i=4: 5-4 = 1 个子数组: [3]
总计：5+1+3+1+1 = 11

代码实现

方法一：单调栈（最优解）

public class Solution {
    /**
     * @param nums: an integer array
     * @return: the number of valid subarrays
     */
    public int validSubarrays(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int n = nums.length;
        int[] nextSmaller = new int[n];
        
        // 初始化，默认右边没有更小的元素
        for (int i = 0; i < n; i++) {
            nextSmaller[i] = n;
        }
        
        // 使用单调递增栈（栈底到栈顶递增）找到下一个更小元素
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            // 当当前元素小于栈顶元素时，栈顶元素的下一个更小元素就是当前元素
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                int index = stack.pop();
                nextSmaller[index] = i;
            }
            stack.push(i);
        }
        
        // 计算总的有效子数组数量
        int count = 0;
        for (int i = 0; i < n; i++) {
            count += nextSmaller[i] - i;
        }
        
        return count;
    }
}

方法二：简化版本（直接在遍历中计算）

public class Solution {
    /**
     * @param nums: an integer array
     * @return: the number of valid subarrays
     */
    public int validSubarrays(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int n = nums.length;
        int count = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = 0; i <= n; i++) {
            // 当到达数组末尾或者当前元素小于栈顶元素时
            while (!stack.isEmpty() && (i == n || nums[i] < nums[stack.peek()])) {
                int index = stack.pop();
                // 当前栈顶元素的下一个更小元素位置是i
                // 以index为起点的有效子数组数量为 i - index
                count += i - index;
            }
            if (i < n) {
                stack.push(i);
            }
        }
        
        return count;
    }
}

方法三：暴力解法（用于理解）

public class Solution {
    /**
     * @param nums: an integer array
     * @return: the number of valid subarrays
     */
    public int validSubarrays(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int n = nums.length;
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            count++; // 单个元素子数组
            
            for (int j = i + 1; j < n; j++) {
                // 检查 nums[i] 是否是子数组 nums[i..j] 中的最小值
                if (nums[j] >= nums[i]) {
                    count++;
                } else {
                    // 一旦遇到比 nums[i] 小的元素，后面的子数组都不满足条件
                    break;
                }
            }
        }
        
        return count;
    }
}

算法分析

方法一/二：单调栈

• 时间复杂度：O(n)，每个元素最多入栈和出栈一次
• 空间复杂度：O(n)，用于存储栈

方法三：暴力

• 时间复杂度：O(n²)，在最坏情况下（数组递增）会达到 O(n²)
• 空间复杂度：O(1)

详细示例演示

以 nums = [3, 1, 2, 4] 为例：

使用方法二（简化版本）：

i=0: stack = [0]
i=1: nums[1]=1 < nums[0]=3, 弹出0, count += 1-0 = 1 (子数组[3])
     stack = [1]
i=2: nums[2]=2 > nums[1]=1, 入栈 stack = [1,2]
i=3: nums[3]=4 > nums[2]=2, 入栈 stack = [1,2,3]
i=4: 结束，弹出所有
     弹出3, count += 4-3 = 1 (子数组[4])
     弹出2, count += 4-2 = 2 (子数组[2], [2,4])
     弹出1, count += 4-1 = 3 (子数组[1], [1,2], [1,2,4])
总计：1+1+2+3 = 7

验证所有有效子数组：

• 从0开始: [3]
• 从1开始: [1], [1,2], [1,2,4]
• 从2开始: [2], [2,4]
• 从3开始: [4]
  合计：1+3+2+1 = 7

总结

1. 关键观察：对于每个起始位置i，有效子数组的终点受到右边第一个比nums[i]小的元素位置的限制
2. 高效解法：使用单调栈在O(n)时间内找到每个元素的下一个更小元素
3. 公式：总数量 = sum(nextSmaller[i] - i) for i = 0 to n-1
4. 边界处理：如果右边没有更小的元素，nextSmaller[i] = n

这个问题的本质是寻找"下一个更小元素"的应用，单调栈是解决这类问题的标准工具。