面一个90年的经理岗，开口要40k+，本来聊得挺顺的。HR总监突然灵魂发问:你这年纪主动离职够有勇气啊。候选人苦笑:公司6个月没发工资了..
程序员老鬼约 4 分钟刚看到个贴子，说有个90年的去面经理岗，聊得挺好，开口要四万多。快谈完了，HR总监来一句：你这年纪还主动离职，胆子不小啊。结果人家苦笑，说原公司已经半年没发工资了，再不走就得饿着了。
我觉得这事吧，重点不在“40k敢不敢要”，而是在“半年没钱发了你还好意思留人”。有些公司一边拖工资，一边要求员工讲忠诚、讲担当，这不是职场，是情感诈骗。
HR担心的是“风险”和“稳定性”，候选人考虑的是“活下去”和“补回来”。放在天平上称一称，谁更有道理，挺明显的。
总的来说还是那句：职场不是讲感情的地方，企业要守底线，打工人也别亏待自己。能保护好自己的，是清醒，不是盲目硬扛。
面试题：区间子数组个数
给你一个整数数组 nums，再给两个整数 left 和 right。问你：有多少个连续子数组，满足这个子数组里的「最大值」在 [left, right] 这个区间里。
注意两个关键词：
是「连续子数组」，不能跳着选 条件看的是「最大值」落不落在区间里
举个简单的例子：
nums = [2, 1, 4, 3], left = 2, right = 3
满足条件的子数组有：
[2] [2,1] [3] [4,3] 不行，因为最大值是 4，大于 right [1,4,3] 也不行，最大值还是 4
最后答案是 3。
暴力想法：枚举所有子数组
最直接的思路就是： 从每个位置出发，把后面的子数组都枚举一遍，同时维护最大值，看它是不是落在 [left, right]。
伪代码脑补一下就是两层 for 循环：外层选起点，内层扩展终点，不断更新 max，然后判断一下。
时间复杂度是多少？O(n^2)。 数组一长，这个就直接寄了，上不了场。
正经做法：一次遍历 O(n) 解决
这个题有个很巧的 O(n) 思路，其实核心就一句话：
把「最大值在 [left, right] 内的子数组个数」拆成：以每个位置结尾的、合法子数组个数之和。
你想象一下从左往右扫数组，扫到 i 这个位置时，问一句：“有多少个以 i 结尾的子数组，它们的最大值在区间里？”
这里需要记三件事：
最近一次出现「> right」的下标（记作 lastGreater） 只要子数组跨过这个位置，它的最大值肯定 > right，直接不合法。最近一次出现「在 [left, right] 区间内」的下标（记作 lastInRange） 子数组必须包含这个位置之一，最大值才有机会落在区间里。对于当前位置 i： 如果lastInRange > lastGreater，说明能构成合法子数组，数量就是lastInRange - lastGreater
为什么？ 因为子数组必须从 (lastGreater, lastInRange] 这个范围中选一个起点，到 i 结束，既不会包含非法的大数（> right），又一定包含一个「在区间内的数」，最大值自然就在 [left, right] 里。
所以一遍扫描，动态维护这两个下标，就能在 O(n) 时间把答案算出来。
Java 代码实现（核心逻辑）
直接上代码，按上面的思路写就行，挺干净的：
publicclassBoundedSubarrayCount{
// 入口方法
publicintnumSubarrayBoundedMax(int[] nums, int left, int right){
int n = nums.length;
int lastInRange = -1; // 最近一次落在 [left, right] 的位置
int lastGreater = -1; // 最近一次 > right 的位置
int ans = 0;
for (int i = 0; i < n; i++) {
int x = nums[i];
// 更新 lastInRange
if (x >= left && x <= right) {
lastInRange = i;
}
// 更新 lastGreater
if (x > right) {
lastGreater = i;
}
// 如果最近一个在区间内的位置，在最近一个超大值之后
// 就能构成若干合法子数组
if (lastInRange > lastGreater) {
ans += lastInRange - lastGreater;
}
// 否则这一位结尾的子数组都是不合法的，贡献为 0
}
return ans;
}
// 简单测一下
publicstaticvoidmain(String[] args){
BoundedSubarrayCount s = new BoundedSubarrayCount();
int[] nums = {2, 1, 4, 3};
int left = 2, right = 3;
System.out.println(s.numSubarrayBoundedMax(nums, left, right)); // 输出 3
}
}
你可以自己在 main 里多加几组数据测一下，比如全都小于 left、全都大于 right、只有一个数落在区间里等等，感受一下三个变量的变化：
lastInRange：一旦遇到区间内的数就往右更新lastGreater：遇到 > right 的数就「清场」，所有跨过它的子数组都失效每一步贡献： max(0, lastInRange - lastGreater)
理解了这三个下标的含义，这题其实就挺顺了，面试里说清楚这个推导过程，基本就够用了。
-END-
我为大家打造了一份RPA教程，完全免费：songshuhezi.com/rpa.html