模拟|双指针

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;
    }
};