仅将流中的最小值和最大值另存为数组

Question

我有一个来自连续流的十进制值流。这些值从一个特定的值开始，然后上升到某个最大值，然后下降到某个最小值（有点像波浪）。值的最大值和最小值并不总是相同的，但可以保证的是，值总是先升后降，然后再升后降，依此类推。

例如，值流可能看起来像：

  0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0, 1.1, 1.2, 1.3, 1.2,
 1.1, 1.0, 0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1, 0.0, 0.1,
 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0, 1.1, 1.0, 0.9, 0.8, 0.7, 0.6, 0.5,
 0.4, 0.3, 0.2, 0.1, 0.0 ...

我需要的是将所有交替的最低和最高值存储到数组中。因此，在以上示例中，最终结果数组应为：

[0.3, 1.3, 0.0, 1.1, 0.0, ...]

这是我尝试使用的算法的伪代码：

var x;
var arr = [];
//listen to stream
//on stream event
void onEvent(double val) {
  if (x == null) {
    x = val;
  }

  if (val > x) {
    if (arr.lastItem < val) {
      arr.push(val);
    }
  } else {
    if (arr.lastItem > val) {
      arr.push(val);
    }
  }
  x=val;
}

最终的最终误差不是预期的结果。有什么更好的解决方案？

Answer 1

希望这可以简单得多，但这是一个解决方案。我们仅创建一个while循环，在仍有可用值时继续。然后，我们找到最小值和最大值，然后将它们从值列表中删除。然后，我们创建一对新的最小和最大值。一旦有了所有最小值和最大值，便可以根据需要将它们映射到双精度值数组。

    public static void main(String[] args) {
        List<Double> values = new ArrayList<>(Arrays.asList(
                0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0, 1.1, 1.2, 1.3, 1.2,
                1.1, 1.0, 0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1, 0.0, 0.1,
                0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0, 1.1, 1.0, 0.9, 0.8,
                0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1, 0.0
        ));

        List<Pair> pairs = new ArrayList<>();

        while (!values.isEmpty()) {
            Double min = values.stream().min(Double::compareTo)
                    .orElseThrow(IllegalStateException::new);

            Double max = values.stream().max(Double::compareTo)
                    .orElseThrow(IllegalStateException::new);

            pairs.add(new Pair(min, max));

            values.remove(min);
            values.remove(max);
        }
        double[] valuesSorted = pairs.stream()
                .map(pair -> new double[] { pair.getMin(), pair.getMax() })
                .flatMapToDouble(Arrays::stream)
                .toArray();
    }

    static class Pair {

        private final double min;

        private final double max;

        Pair(double min, double max) {
            this.min = min;
            this.max = max;
        }

        public double getMin() {
            return min;
        }

        public double getMax() {
            return max;
        }

        @Override
        public String toString() {
            return "Pair{" +
                    "min=" + min +
                    ", max=" + max +
                    '}';
        }
    }

输出

[0.0, 1.3, 0.0, 1.2, 0.1, 1.2, 0.1, 1.1, 0.1, 1.1, 0.2, 1.1, 0.2, 1.0, 0.2, 1.0, 0.3, 1.0, 0.3, 1.0, 0.3, 0.9, 0.3, 0.9, 0.4, 0.9, 0.4, 0.9, 0.4, 0.8, 0.4, 0.8, 0.5, 0.8, 0.5, 0.8, 0.5, 0.7, 0.5, 0.7, 0.6, 0.7, 0.6, 0.7, 0.6, 0.6]