如何在TreeMap中获取小于指定值的首个条目键（仅用键操作）

问题背景 #

用TreeMap存储某产品的每日库存，键为日期，值为库存，初始化代码如下：

NavigableMap<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < stocks.size(); i++) {
    map.put(i+1, stocks.get(i));
}

库存数据如下：

需求：

• 获取值小于指定数的首个条目（即值最大的符合条件项中，日期最早的键）：比如找值小于4时返回8，找值小于7时返回2；
• 限制：不能遍历所有值，只能通过键相关操作实现。

解决方案 #

仅靠原TreeMap无法实现这个需求——TreeMap是按键的自然顺序排序的，值的分布完全无序，没有办法通过键的导航方法（比如lowerKey()、ceilingKey()）直接关联到值的条件。必须额外维护一个按值排序的结构，同时保证相同值下保留最早的日期键。

具体实现 #

1. 定义自定义类，存储库存值和对应最早日期，并重写比较规则：

class StockEntry implements Comparable<StockEntry> {
    int stockValue;
    int earliestDate;

    public StockEntry(int stockValue, int earliestDate) {
        this.stockValue = stockValue;
        this.earliestDate = earliestDate;
    }

    @Override
    public int compareTo(StockEntry other) {
        // 先按库存值升序，值相同时按日期升序（确保最早的日期排在前面）
        int valueCompare = Integer.compare(this.stockValue, other.stockValue);
        if (valueCompare != 0) {
            return valueCompare;
        }
        return Integer.compare(this.earliestDate, other.earliestDate);
    }
}

2. 初始化TreeMap的同时，维护一个TreeSet存储排序后的StockEntry：

NavigableMap<Integer, Integer> stockMap = new TreeMap<>();
TreeSet<StockEntry> sortedStockEntries = new TreeSet<>();

// 假设stocks是存储每日库存的List
for (int i = 0; i < stocks.size(); i++) {
    int date = i + 1;
    int stock = stocks.get(i);
    stockMap.put(date, stock);

    StockEntry newEntry = new StockEntry(stock, date);
    // 检查是否已有相同库存值的条目，只保留日期最早的
    StockEntry existingEntry = sortedStockEntries.floor(newEntry);
    if (existingEntry != null && existingEntry.stockValue == stock) {
        // 当前日期比已有的晚，无需添加
        continue;
    }
    // 移除所有相同库存值但日期更晚的条目
    while (true) {
        StockEntry higherEntry = sortedStockEntries.higher(newEntry);
        if (higherEntry != null && higherEntry.stockValue == stock) {
            sortedStockEntries.remove(higherEntry);
        } else {
            break;
        }
    }
    sortedStockEntries.add(newEntry);
}

3. 查询逻辑
   要找值小于target的首个条目，直接用TreeSet的lower()方法：

public Integer getEarliestDateWithStockLessThan(int target) {
    // 构造目标条目，用最大日期确保匹配所有值小于target的条目
    StockEntry targetEntry = new StockEntry(target, Integer.MAX_VALUE);
    StockEntry resultEntry = sortedStockEntries.lower(targetEntry);
    return resultEntry != null ? resultEntry.earliestDate : null;
}

验证 #

• 调用getEarliestDateWithStockLessThan(4)：返回8，符合需求；
• 调用getEarliestDateWithStockLessThan(7)：返回2（值小于7的最大有效值是6，对应的最早日期是2），符合需求。

补充说明 #

• 该方案的插入和查询操作均为O(log n)时间复杂度，无需遍历所有值；
• 如果不允许额外维护结构，仅用原TreeMap的话，无法满足“不遍历值”的限制——必须逐个检查值的条件，违反限制。

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