Алгоритм All nearest smaller values ( все ближащие меншие значения) на Java
Алгоритм All nearest smaller values ( все ближащие меншие значения) на Java
 
В информатике задача поиска всех ближайших меньших значений - это следующая задача: для каждой позиции в последовательности чисел выполнить поиск от первой до последней позиции, содержащей меньшее значение. Эту проблему можно эффективно решить как параллельными, так и непараллельными алгоритмами: Berkman, Schieber & Vishkin (1993), который первым определил процедуру как полезную подпрограмму для других параллельных программ, разработал эффективные алгоритмы ее решения на Parallel Random Access Machine model; Она также может быть решена в линейное время на непараллельном компьютере с использованием алгоритма на основе стека. Позже исследователи изучили алгоритмы его решения в других моделях параллельных вычислений.

Предположим, что входной сигнал является двоичной последовательностью Ван-дер-Корпута

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15.

Первый элемент последовательности (0) не имеет предыдущего значения. Ближайшее (единственное) меньшее значение, предшествующее 8 и 4, равно 0. Все три значения, предшествующие 12, меньше, но ближайшим является 4. Продолжая таким же образом, ближайшие меньшие значения для этой последовательности (указывающие на несуществование Предыдущего меньшего значения с помощью дефиса), равны

-, 0, 0, 4, 0, 2, 2, 6, 0, 1, 1, 5, 1, 3, 3, 7.

В большинстве приложений должны вычисляться положения ближайших меньших значений, а не сами значения, и во многих приложениях один и тот же расчет должен быть вычислен для обращения последовательности, чтобы найти следующее меньшее значение, наиболее близкое к последовательность.

Далее представлен алгоритм решения задачи с реализацией на Java


import java.util.*;
public class AllNearestSmallerValues {
    // https://en.wikipedia.org/wiki/All_nearest_smaller_values
    public static int[] nsv(int[] a) {
        int n = a.length;
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            int j = i - 1;
            while (j != -1 && a[j] >= a[i]) {
                j = p[j];
            }
            p[i] = j;
        }
        return p;
    }
    public static long maxInscribedRectangle(int[] heights) {
        int n = heights.length;
        int[] rheights = new int[n];
        for (int i = 0; i < n; i++) {
            rheights[i] = heights[n - 1 - i];
        }
        int[] lnsv = nsv(heights);
        int[] rnsv = nsv(rheights);
        long res = 0;
        for (int i = 0; i < n; i++) {
            int a = lnsv[i] + 1;
            int b = n - 1 - rnsv[n - 1 - i] - 1;
            long cur = (long) (b - a + 1) * heights[i];
            res = Math.max(res, cur);
        }
        return res;
    }
    public static long maxInscribedRectangle2(int[] heights) {
        long res = 0;
        Stack<Integer> spos = new Stack<>();
        Stack<Integer> sh = new Stack<>();
        sh.push(0);
        for (int i = 0; i <= heights.length; i++) {
            int h = i < heights.length ? heights[i] : 0;
            int pos = i;
            while (sh.peek() > h) {
                pos = spos.pop();
                res = Math.max(res, (long) sh.pop() * (i - pos));
            }
            spos.push(pos);
            sh.push(h);
        }
        return res;
    }
    // Usage example
    public static void main(String[] args) {
        System.out.println(maxInscribedRectangle(new int[]{1, 2, 3}));
        System.out.println(maxInscribedRectangle2(new int[]{1, 2, 3}));
        System.out.println(Arrays.toString(nsv(new int[]{1, 1, 3, 2})));
        Random rnd = new Random(1);
        for (int step = 0; step < 1000; step++) {
            int n = rnd.nextInt(10) + 1;
            int[] h = rnd.ints(n, 0, 10).toArray();
            long res1 = maxInscribedRectangle(h);
            long res2 = maxInscribedRectangle2(h);
            if (res1 != res2)
                throw new RuntimeException();
        }
    }
}

359