模拟|双指针

lc941山脉数组

class Solution {
public:
bool validMountainArray(vector<int>& arr) {
int n = arr.size();
int i = 0;
if (n < 3) return false;
// 上升
while (i < n - 1 && arr[i] < arr[i + 1]) 
i++;


if (i == 0 || i == n - 1) 
return false; 

// 下降
while (i < n - 1 && arr[i] > arr[i + 1]) 
i++;


return i == n - 1; 
}
};

lc475

双指针 max(min)

 class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
sort(houses.begin(), houses.end());
sort(heaters.begin(), heaters.end());

// 在供暖器前后插入哨兵，简化边界判断
heaters.insert(heaters.begin(), INT_MIN);
heaters.push_back(INT_MAX);

        int n = houses.size();
// 用 dic 数组存储每个房屋到最近供暖器的距离
vector<long long> dic(n); 
int cur = 0;
int heaterSize = heaters.size();

        for (int i = 0; i < n; i++) {
// 找到第一个位置 >= 当前房屋的供暖器（含哨兵）
while (cur < heaterSize && heaters[cur] < houses[i]) {
cur++;
}
// 计算当前房屋到最近供暖器的距离
long long dist = min(
(long long)heaters[cur] - houses[i], 
(long long)houses[i] - heaters[cur - 1]
);
dic[i] = dist;
}

        // 返回所有房屋距离的最大值，即最小加热半径
return *max_element(dic.begin(), dic.end());
}
};

lc403

记忆化搜索，剪枝

class Solution {
public:
vector<int> stones;
unordered_set<int> s;
bool canCross(vector<int>& stones) {
this->stones = stones;
return dfs(0, 0);
}
bool dfs(int k, int idx)
{
int key = idx * 1000 + k;
if (s.count(key) != 0) {
return false;
} else {
s.insert(key);
}

        vector<int> steps = {k - 1, k + 1, k};
for (int step : steps) {
if (step <= 0) continue;
int target = stones[idx] + step;
for (int i = idx + 1; i < stones.size(); ++i) {
if (stones[i] == target) {
if (dfs(step, i)) {
return true;
}
break;
} else if (stones[i] > target) {
break;
}
}
}

        return idx == stones.size() - 1;
}
};