双指针技巧（快慢指针）中贪心算法的应用及示例咨询

Great question! It’s totally normal to feel confused when the term "greedy" pops up in a different context than the classic greedy algorithms you might have learned. Here, we’re not talking about building Huffman trees or activity selection—instead, we’re leveraging the core greedy idea: making the locally optimal choice at each step to reach a globally optimal solution. Let’s break down how this applies to two-pointer problems, with concrete examples tied to your original removeElement code.

1. In-Place Element Filtering/Removal (Your Original Example) #

Your removeElement code is a perfect example of greedy thinking in two-pointer problems. Here’s how it works:

• Local Optimal Choice: For every element the fast pointer encounters, if it’s not equal to val, we place it at the slow pointer’s position. This ensures that at each step, the subarray from the start to the slow pointer contains only valid elements (those not equal to val).
• Global Optimal Result: By repeating this for all elements, the slow pointer’s final index gives us the length of the filtered array—all valid elements are packed at the start of the original array, with no extra space used.

Your original code:

public int removeElement(int[] nums, int val) { 
    int k = 0; 
    for (int i = 0; i < nums.length; ++i) { 
        if (nums[i] != val) { 
            nums[k] = nums[i]; 
            k++; 
        } 
    } 
    return k; 
}

Similar Example: Remove Duplicates from Sorted Array #

This uses the same greedy logic—we only keep unique elements by updating the slow pointer whenever we encounter a new value:

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int slow = 0;
    for (int fast = 1; fast < nums.length; fast++) {
        // Local optimal: keep only unique elements in the slow pointer's range
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
}

2. Two Sum (Sorted Array) #

For sorted arrays, the two-pointer approach uses greedy logic to narrow down to the target sum efficiently:

• Local Optimal Choice: Start with pointers at the start and end of the array. If their sum is larger than the target, move the right pointer left (to reduce the sum). If the sum is smaller, move the left pointer right (to increase the sum). Each step makes the best possible adjustment to get closer to the target.
• Global Optimal Result: Since the array is sorted, this approach guarantees we’ll find the pair (if it exists) in linear time, without checking all possible pairs.

public int[] twoSum(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {
            return new int[]{left + 1, right + 1}; // 1-indexed result
        } else if (sum > target) {
            right--; // Local optimal: reduce sum by moving right pointer left
        } else {
            left++; // Local optimal: increase sum by moving left pointer right
        }
    }
    return new int[]{-1, -1}; // No valid pair found
}

3. Interval Merging #

Interval merging relies on greedy sorting and two pointers to combine overlapping intervals:

• Local Optimal Choice: First sort intervals by their start time. Then, use a slow pointer to track the current merged interval. For each interval the fast pointer encounters, if it overlaps with the current merged interval, update the merged interval’s end to the maximum of the two ends (merge them). If it doesn’t overlap, add the current merged interval to the result and move the slow pointer to the fast pointer’s position.
• Global Optimal Result: This ensures we merge all possible overlapping intervals in one pass, resulting in the minimal set of non-overlapping intervals.

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

public int[][] merge(int[][] intervals) {
    if (intervals.length == 0) return new int[0][];
    // Greedy sort: sort intervals by their start time first
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    List<int[]> merged = new ArrayList<>();
    int slow = 0;
    for (int fast = 1; fast < intervals.length; fast++) {
        if (intervals[fast][0] <= intervals[slow][1]) {
            // Local optimal: merge into the largest possible interval
            intervals[slow][1] = Math.max(intervals[slow][1], intervals[fast][1]);
        } else {
            merged.add(intervals[slow]);
            slow = fast;
        }
    }
    merged.add(intervals[slow]);
    return merged.toArray(new int[merged.size()][]);
}

4. Container With Most Water #

This problem uses greedy two-pointer logic to find the maximum area of water a container can hold:

• Local Optimal Choice: Start with pointers at both ends. The area is determined by the shorter height and the distance between pointers. To maximize area, we move the pointer pointing to the shorter height—moving the taller pointer would only decrease the width without increasing the height, so it can’t lead to a larger area.
• Global Optimal Result: By always choosing to move the shorter pointer, we explore all possible pairs that could yield a larger area, ending up with the maximum possible value.

public int maxArea(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int maxArea = 0;
    while (left < right) {
        int currentArea = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, currentArea);
        // Local optimal: move the pointer with the shorter height
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
}

Key Takeaway #

In two-pointer problems, the "greedy" part isn’t about complex algorithms—it’s about making the best possible choice at each step that brings you closer to the final goal, without needing to backtrack. Every example above uses this core idea to guide how the two pointers move, leading to efficient, linear-time solutions.

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